鸽巢定理的简单形式
鸽巢原理（抽屉原理）：如果有n+1个鸽子要进n个鸽巢，则至少存在一个鸽巢种包含两个或更多的鸽子。
看上去是一句“废话”，不过这句”废话“在用来证明一个排列或则某种现象的存在性上相当有魅力！
关于鸽巢原理更抽象的表述：
• If X has more elements than Y, then f is not one-to-one.
• If X and Y have the same number of elements and f is onto, then f is one-to-one.
• If X and Y have the same number of elements and f is one-to-one, then f is onto.
•中国剩余定理上有关鸽巢定理的证明
令m，n为互素的正整数，并令a，b为两个整数，且0 <= a <= n – 1, 0 <= b <= n – 1。Therefore，存在一个正整数x，使得x mod m = a 并且 x mod n = b；即写成x = pm + a, x = qn + b。这里p和q是两个整数。
证明：
首先考虑n个整数
a, m + a, 2*m + a, 3*m + a, … , (n – 1)*m + a;
这些整数中每个数除以m都余a。设其中两个除以n有相同的余数r。令这两个数为i*m + a, j*m + a。(0 <= i < j <= n – 1)。因此，存在两个整数qi, qj使得
i * m + a = qi * n + r ———- (1)
j * m + a = qj * n + r ———–(2)
整理得
(j – i)*m = (qj – qi)*n ————(3)
从(3)式可以看出n是(j – i)*m的因子，因为n和m互素。所以n是(j – i)的因子。然而 0 <= i < j <= n – 1 即 0 < j – i <= n – 1，也就是说n不可能是j – i的因子。这和之前的假设：n个整数a, m + a, 2*m + a, 3*m + a, … , (n – 1)*m + a;中有两个除以n会有相同的余数。因此可以确定：这n个数中每一个除以n都有不同的余数。根据鸽巢原理：n个数，0，1，…，n – 1中的每一个数作为余数都要出现；特别的数b也会出现。令p为整数，满足0 <= p <= n – 1 ，且使数x = pm + a 除以n的余数为b。则对于某个特定的数q：
x = q*n + b
到此得证中国剩余定理。
鸽巢原理的加强形式
定理: 令q1， q2, q3, …., qn为正整数。如果将 q1， q2, q3, …., qn – n + 1 个物体放到n个盒子中，则存在一个i，使得第i个盒子至少含有qi个物品 ；
证明: 假设将q1， q2, q3, …., qn – n + 1个物品分别放到n个盒子里。如果每一个i (i = {1, 2, ..n})，第i个盒子中放少于qi 个物品，则所有盒子所放物品的总数不超过
(q1 – 1) + (q2 – 1) + … + (qn – 1) = q1 + q2 + … + qn – n
显然，比所要放的总数少一个。因此可以确定，对某个i (i = {1, 2, .. n})，第i个盒子至少包含qi个物品。
转载于:https://www.cnblogs.com/vongang/archive/2012/03/29/2423723.html