鸽巢原理，又名狄利克雷抽屉原理、鸽笼原理。

其中一种简单的表述法为：

• 若有n个笼子和n+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少2只鸽子。

另一种为：

• 若有n个笼子和kn+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少k+1只鸽子。

拉姆齐定理是此原理的推广。

目录

• 1 例子

• 2 推广

• 3 数学证明

• 4 无穷集中的情况

• 5 来源

• 6 外部链接

例子

虽然鸽巢原理看起来很容易理解，但有时使用鸽巢原理会得到一些有趣的结论：

• 比如：北京至少有两个人头发数一样多。

• 证明：常人的头发数在15万左右，可以假定没有人有超过100万根头发，但北京人口大于100万。如果我们让每一个鸽巢对应一个头发数字，鸽子对应于人，那就变成了有大于100万只鸽子要进到至多100万个巢中。所以，可以得到“北京至少有两个人头发数一样多”的结论。

另一个例子：

• 盒子里有10只黑袜子、12只蓝袜子，你需要拿一对同色的出来。假设你总共只能拿一次，只要3只就可以拿到相同颜色的袜子，因为颜色只有两种（鸽巢只有两个），而三只袜子（三只鸽子），从而得到“拿3只袜子出来，就能保证有一双同色”的结论。

更不直观一点的例子：

• 有n个人（至少2人）互相握手（随意找人握），必有两人握手次数相同。

• 这里，鸽巢对应于握手次数，鸽子对应于人，每个人都可以握[0,n-1]次（但0和n-1不能同时存在，因为如果一个人不和任何人握手，那就不会存在一个和所有其他人都握过手的人），所以鸽巢是n-1个。但有n个人（n只鸽子），因此证明了命题正确。

鸽巢原理经常在计算机领域得到真正的应用。比如：哈希表的重复问题（冲突）是不可避免的，因为Keys的数目总是比Indices的数目多，不管是多么高明的算法都不可能解决这个问题。这个原理，还证明任何无损压缩算法，在把一个文件变小的同时，一定有其他文件增大来辅助，否则某些信息必然会丢失。

推广

一种表达是这样的：如果要把n个物件分配到m个容器中，必有至少一个容器容纳至少?n / m?个物件。（?x?大于等于x的最小的整数）

数学证明

设把n＋1个元素分为n个集合 ，记 表示这n个集合里相应的元素个数。

假设

因为

所以

所以

这与题设矛盾，因此结论得证。

无穷集中的情况

借由康托的无穷基数可将鸽巢原理推广到无穷集中。

来源

• Grimaldi, Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. 4th edn. 1998. ISBN 0-201-19912-2. pp. 244–248.

• Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "Pigeonhole principle". In Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics. Electronic document, retrieved 11 November 2006.

• 抽屉原理

外部链接

• "The strange case of The Pigeon-hole Principle"; Edsger Dijkstra investigates interpretations and reformulations of the principle.

• "The Pigeon Hole Principle"; Elementary examples of the principle in use by Larry Cusick.

• "Pigeonhole Principle from Interactive Mathematics Miscellany and Puzzles"; basic Pigeonhole Principle analysis and examples by Cut-the-Knot.

• "The Puzzlers‘ Pigeonhole"; Cut-the-Knot on the importance of the principle in the field of puzzle solving and analysis.

鸽巢原理