鸽笼原理的叙述十分简单:有10只鸽子飞进9个笼子,那么无论如何总会有一个笼子有2只或者2只以上的鸽子。更一般地,如果有至少只鸽子飞进
个笼子,则无论如何总会有一个笼子有
只或者
只以上的鸽子。
用反证法可以很容易地给出鸽笼原理的证明。反证,假设每个笼子的鸽子数目都不超过,那么
个笼子的总共的鸽子数目将会不超过
,与总共至少有
只鸽子矛盾。从而会有一个笼子有
只或者
只以上的鸽子。这样就完成了证明。
虽然鸽笼原理的叙述以及证明都非常简单,但是在数学中却发挥着极其重要的作用,尤其是在存在性的证明中。例如,利用鸽笼原理可以很容易证明如下的定理:
假设认识是相互的(即不存在甲认识乙,乙不认识甲这种情况。),那么全世界任意六个人总有三个人互相都彼此认识或者有三个人互相都彼此不认识。
证明:随便选取6个人中的1个,称其为甲,显然对于其余个人,甲要么认识要么不认识。这样就构成了认识和不认识两个笼子,其余
个人看作
只鸽子,那么将
只鸽子放入
个笼子,必然会有一个笼子装有至少
只鸽子。不妨设这个笼子是认识,这3只鸽子称作乙、丙、丁。那么甲认识乙、丙、丁,接下来考虑乙、丙、丁之间是否认识。如果乙、丙、丁之间存在两个人互相认识,不妨设为乙和丙,那么就找到了甲、乙、丙,这三个人互相认识。接下来剩下的唯一一种情形就是乙、丙、丁三个人两两不认识。于是找到了三个人互相都不认识。这样就完成了证明。
鸽笼原理在计算机领域也有广泛的应用。例如,由鸽笼原理可知,散列表的重复问题是不可避免的;任何无损压缩算法在把一个文件变小的同时必有其他文件的增大来辅助。