鸽巢原理
本章参考
Pigeonhole Principle Theorem
如果 “A” 是每个洞的平均鸽子数量，其中 A 不是整数，那么
至少有一个鸽笼必须包含 ≥ ⌈A⌉只鸽子。（向上取整函数）
剩余的鸽舍每个必须包含 ≤ ⌊A⌋只鸽子。（向下取整函数）
例1
考虑有 Kn+1 只鸽子，n 个巢。容易知道平均 K+1/n 只鸽子，然后至少有一个会有K+1个鸽子。
也就是说，要确保至少有一个鸽舍容纳 (K+1) 只鸽子，所需的最小鸽子数量为 (Kn+1)。
例2
一个袋子里装有 10 个红色弹珠、10 个白色弹珠和 10 个蓝色弹珠。从袋子里随机挑选至少多少个弹珠，才能保证挑选出 4 个颜色相同的弹珠？
要造出来的 K+1 = 4, 由例1得最少拿取 Kn+1 = 10 个。
Pigeonhole Principle Strong Form Theorem
第 1 个盒子希望它至少有 q1 个，第 2 个盒子希望它至少有 q2 个......第 n 个希望 qn 个。
那么放多少个物体，才能保证“至少有一个盒子达到它自己的阈值”？
答案：q1 + q2 + ⋯ + qn − n + 1
例1
在计算机科学系，学生社团可以由 10 名一年级学生、8 名二年级学生、6 名三年级学生或 4 名四年级学生组成。为了确保能够成立一个学生社团，我们至少需要从系里随机抽取多少名学生？
答案：10 + 8 + 6 + 4 − 3 + 1
例2
一个盒子里装有 6 个红球、8 个绿球、10 个蓝球、12 个黄球和 15 个白球。为了确保取出的球中有 9 个颜色相同，我们至少要从盒子里随机取出多少个球？
我们目标都是 9 个，但是红色和绿色达不到这个数目，于是鸽巢原理只能对其他的颜色来做。但是“至少”，运气最差，必须要把前面的全部取完先。
答案：6 + 8 + (9 + 9 + 9 - 3 + 1)
题题
1
证明在任意 52 个整数中，总有两个整数的差能被 51 整除。
提示：取模
2
证明对于任意 101 个不同的实数的序列，总存在长度至少为 11 的递增或递减子序列。
做法：假设序列总小于等于 10.
对于第 i 个数字，设计 D[i] 和 I[i]，表示以 a
观察到，对于 j ∈ {1,2,...i-1} 总有 a
但是如果长度小于等于 10，那么 D 和 I 只能取 1 ~ 10，总共就 100 种组合，无法代表 101 个数字。矛盾。
原假设错误，故得证。
3
在 6 个人中，证明至少有 3 个人是共同的朋友或共同的陌生人。
曲棍球杆恒等式（Hockey Stick Identity）
定理陈述
对任意非负整数 (r, M)，有：
C(r,r) + C(r+1,r) + C(r+2,r) + ... + C(r+M,r) = C(r+M+1,r+1)