鸽笼原理英文是Pigeonhole Principle。但是它有很多中文名字，比如鸽巢原理，抽屉原理，鞋盒原理等等。它指的是如下一个定理：
如果n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或更多的物体。
我们来证明一下(这不是显然么！)。用反证法。假设每个盒子中都至多有一个物体，那么物体的总数至多是n。这与共有n+1个物体矛盾。所以定理成立。
别看这个定理很简单，用它却可以巧妙的解决很多问题，一个简单的例子就是13个人中至少有两个人的生日在同一个月份里。下面我们来考虑一些更具挑战性的例子：
1 证明给定m个整数a1,a2,…,am，存在整数k和l，0<=k<l<=m，使得a(k+!)+a(k+2)+…+a(l)能够被m整除。
证明：对于m个和 a1 , a1+a2 , a1+a2+a3 , … , a1+a2+…+am 。如果这些和当中的任意一个可以被m整除，问题便得证了。假设这m个和都不整除m，那么它们除以m的余数可能是1,2,…,m-1。由于存在m个数，而余数只有m-1种，所以必然有两个和除以m有相同的余数(鸽笼原理)。因此存在整数k和l，0<=k<l<=m，使得a1+a2+…+ak=bm+r , a1+a2+…+al=cm+r，两式相减，得到a(k+!)+a(k+2)+…+a(l)=(c-b)m，从而命题得证。
2 距离全国大学生数学建模竞赛还有11周时间。我决定每天至少做一道建模题，但为了不让自己陷入题海战略，给自己一些总结和思考的时间，我还是决定每周不能做题超过12道。证明存在连续的若干天，期间我恰好做了21道题。
证明：令a1是我第一天做的题数，a2是第一天和第二天做的总题数，a3是第一天、第二天和第三天做的总题数…。由于每天我至少做一道题，故数列an严格单调递增。由于每周做题不超过12道，所以a77<=12*11=132。因此有1<=a1<a2<a3<…<a77<=132。把上面的不等式每项加上21，得到：22<=a1+21<a2+21<a3+21<…<a77 + 21<=132+21=153。于是这154个数：a1,a2,…,a77,a1+21,a2+21,…,a77 +21 中的每个数都是1到153之间的一个整数。所以它们中有两个相等(鸽笼原理)。由于前77项严格单调递增，后77项也严格单调递增，所以相等的项一定是前77项中的一个和后77项中的一个。用数学语言来说，存在 i,j(i>j) 使得ai=aj+21。从而我在第j+1,j+2,…,i天做了21道题。
3 最后，我们来用鸽笼原理证明中国剩余定理。中国剩余定理：m,n为两个互素(互质)的正整数，a和b是两个整数，满足0<=a<=m-1以及0<=b<=n-1。则存在一个正整数x使得x除以m余a,除以n余b。
证明：我们的证明思路就是要找到这样一个x。首先考虑n个整数：a,m+a,2m+a,…,(n-1)m+a，显然这n个整数除以m都余a。假设其中的两个数，im+a和jm+a(0<=i<j<=n-1) 除以n有相同的余数r，即存在两个整数p,q使得，im+a=pn+r , jm+a=qn+r 两式相减，得 (j-i)m=(q-p)n 这说明n是(j-i)m 的一个因子。由于m,n互素，所以n是j-i 的因子。但j-i<=n-1，n不可能是j-i 的因子。矛盾！因此假设不成立。即上述n个整数除以n都有不同的余数。于是0,1,2,…,n-1的每一个作为余数都要出现(鸽笼原理)。注意到0<=b<=n-1，所以b一定会作为余数出现。令p为整数，满足0<=p<=n-1，且使数pm+a除以n的余数为b。则存在q使得pm+a=qn+b，令x=pm+a=qn+b。则我们找到了这样的x,使得它除以m余a,除以n余b。
更抽象一点来说，鸽笼原理从集合论上描述如下：
S1,S2为两个有限集合，令映射f:S1->S2是一个从S1到S2的函数。(函数要求比映射高，因为它要求S1中的任何元素的像唯一)
以下描述等价，均为鸽笼原理：
1 如果|S1|>|S2|，那么f就不是一对一(one on one)的。(|S1|表示S1的模，即S1中元素个数)
2 如果|S1|=|S2|，并且f是映上的(不太会表达啊，用英文说是f maps S1 onto S2)，那么f就是一对一的。
3 如果|S1|=|S2|，并且f是一对一的，那么f就是映上的。
参考文献：Richard A.Brualdi:Introductory Combinatorics Fourth Edition,Pearson Education 2004
相关日志:
很好玩。
[Reply]
one on one应该译为”一一对应”或”双射”，bijections。
onto functions (or surjections)，是”到上映射“或”满射”。
[Reply]
Charlesgao 回复 :
牛人!非常感谢！
[Reply]
hey,怎么没接着写下去了？
[Reply]
Charlesgao 回复 :
本来想暑假多写几篇着…
可惜又有任务啦
命苦啊
[Reply]
我来说两句：