鸽巢原理

最近要给小孩子们讲课，有一题用到了生成函数，没学过，看似是组合数学当中的内容，于是学习了一下组合数学相关内容，鸽巢原理是其中入门的知识之一

鸽巢原理：

把\(n+1\)个球放进\(n\)个盒子中，一定会存在一个盒子中的球数量\(\geq 2\)
反证：假设\(n\)个盒子中球的数量都\(<2\)，那么\(n\)个盒子中的球数最多为\(n\) \(< n+1\)
推广：将\(m\)个球放进\(n\)个盒子中，一定会存在一个盒子中的球的数量$\geq \lceil \frac{m}{n} \rceil $ (证明方法类似)

1.忘记啥结论了
2.已知\(1500\)个人生在同一年，一定存在至少\(5\)个人生在同一天
3.\(n\)个人之间互相握手(一个人可以自由选择与谁发生握手，也可以和谁都不握手)，一定会存在至少\(2\)个人的握手次数相等

Ramsey定理

说明：https://baike.baidu.com/item/拉姆塞理论/6691261?fr=aladdin
狭义：当一个集会中人数\(\geq 6\)时，一定存在\(3\)人彼此认识或\(3\)人彼此不认识 (Ramsey的这个结论记住就行，其他的好像用不太上)；
集会中的人看作图中节点，认识看作红色边，不认识看作蓝色边，人与人之间的关系一定是认识/不认识其中之一，所以可以构成一个完全图，该命题可看作：\(6\)阶及\(6\)阶以上的完全图，一定包含红色或蓝色的\(3\)阶完全图；我们将一定包含\(n\)阶红色或蓝色完全图的最小阶染色完全图的阶数计做\(r(n, n)\)
推广：一定包含s阶红色完全图或t阶蓝色完全图的最小阶染色完全图的阶数计做\(r(s, t)\)，有\(r(s, t) = r(t, s); r(2, n) = r(n, 2) = n\)

相关题目

hdu 5917：由Ramsey定理，\(\geq 6\)人的集合都有贡献，\(\leq 5\)人的集合暴力枚举(按照第\(k+1\)层枚举位置\(>\)第\(k\)层枚举位置的方式，得到的是组合而不是排列)
hdu 6152：由Ramsey定理，\(\geq 6\)人的集合都是bad team，\(\leq 5\)人的暴力枚举，每个集合中遍历各顶点判定是否存在纯色三角形
poj 2356：前缀和+鸽巢原理，存在对\(m\)取模为0的就是答案，如果不存在，由鸽巢原理，剩余\(1\)到\(m-1\)中必有\(2\)个不同的前缀和模\(m\)相等，减去公共部分后剩余部分的和模\(m\)一定为\(0\)
poj 3370：前缀和+鸽巢原理
hdu 1808：前缀和+鸽巢原理
hdu 3183：这个看似跟鸽巢原理无卵关系，单调队列维护非降序列，每次遇到小于队尾元素时，将队尾元素出队，并对剩余次数-1，都入队后如果还有剩余次数，从队尾逐个出队就好
hdu 5776：前缀和+鸽巢原理，求各前缀和\(\mod m\)，如果模为\(0\)的前缀和存在，或存在\(>1\)个前缀和的模相等则yes，否则no