鸽巢原理

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

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

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

另一种为：

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

集合论的表述如下：

若A是n+1元集，B是n元集，则不存在从A到B的单射。

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

例子[编辑]

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

比如：北京至少有两个人头发数一样多。
- 证明：常人的头发数目在15万左右，可以假定没有人有超过100万根头发，但北京人口大于100万。如果把每个鸽巢定义为“头发的数量”，便共有100万个鸽巢。打一个比方，一根头发的人就会被编排在一根头发属于的巢、两根就在两根头发属于的巢，如此类推。鸽子则对应于人，那就变成了有大于100万只鸽子要进到100万个巢中（另一种说法是把多于100万个人编排到他们身上头发所属的鸽巢，比如有一个人有三根头发，他便会进了属于有三根头发的人的鸽巢）。因为北京人口多于100万，如果受访的前100万人头发数目刚好不同，第100万零一个的北京市民就必定会进了一个已经有一人在内的鸽巢。因此，我们便可以得到“北京至少有两个人头发数一样多”的结论。

另一个例子：

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

另一个例子：

某男性先后有过4位妻子，合共生有2子3女，则至少有2位子女有同一位母亲，且至少1位妻子没有女儿，至少2位妻子没有儿子。
- 至少有2位子女有同一位母亲 → 若非如此，即任何2位子女都没有相同的母亲，则该男性至少要有5位妻子，矛盾。
- 至少1位妻子没有女儿 → 若非如此，即每位妻子都有女儿，则该男性至少要有4位女儿，矛盾。
- 至少2位妻子没有儿子 → 若非如此，即最多1位妻子没有儿子，则该男性至少要有3位儿子，矛盾。

更不直观一点的例子：

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

鸽巢原理经常在计算机领域得到真正的应用。比如：哈希表的重复问题（冲突）是不可避免的，因为Keys的数目总是比Indices的数目多，不管是多么高明的算法都不可能解决这个问题。这个原理，还证明任何无损压缩算法，在把一些输入变小的同时，作为代价一定有其他的输入增大，否则对于长度为L的输入集合，该压缩算法总能将其映射到一个更小的长度小于L的输出集合，而这与鸽巢理论相悖。

推广[编辑]

一种表达是这样的：如果要把n个对象分配到m个容器中，必有至少一个容器容纳至少 $\left\lceil {\frac {n}{m}}\right\rceil$ 个对象。

数学证明[编辑]

反证法[编辑]

设把n+1个元素分为n个集合 $A_{1},A_{2},\cdots ,A_{n}$ ，记 $a_{i}=|A_{i}|(i=1,2,\cdots ,n)$ 表示这n个集合里相应的元素个数。

假设 $\forall a_{i}<2(i=1,2,\cdots ,n)$

因为 $a_{i}\in \mathbb {N}$

所以 $a_{i}\leq 1$

所以 $a_{1}+a_{2}+\cdots +a_{n}\leq 1+1+\cdots +1=n<n+1$

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

概率方法[编辑]

将m个元素随机放入n个集合 $A_{k}$ 中(m > n)。规定 $\left\lceil {\frac {m}{n}}\right\rceil ={\frac {m}{n}}$ 如果n整除m。随机选择一个集合，它的大小的期望是： $\sum _{k=1}^{n}|A_{k}|{\frac {1}{n}}={\frac {|A_{1}|+|A_{2}|+\cdots +|A_{n}|}{n}}={\frac {m}{n}}$ 由于 $|A_{k}|$ 只能是整数，所以必有一个m，使得 $|A_{m}|\geq \left\lceil {\frac {m}{n}}\right\rceil$

更强的形式[编辑]

设 $q 1, q 2, ..., q n$ 皆是正整数，现有

q_{1}+q_{2}+\cdots +q_{n}-n+1

个对象要分配在 $n$ 个箱子中，那么以下叙述至少一者成立：

第1个箱子包含至少 $q 1$ 个对象；
第2个箱子包含至少 $q 2$ 个对象；
......
第 $n$ 个箱子包含至少 $q n$ 个对象。^[1]

这个原理一样可以使用反证法证明，即假设上述所有叙述为假并得出矛盾，方法与前述简单情况类似。

无穷集中的情况[编辑]

借由康托的无穷基数可将鸽巢原理推广到无穷集中：如果集合A的势大于集合B的势，那么不存在由A到B的单射。

参见[编辑]

其他组合原理，如：
- 容斥原理
- 乘法原理

参考资料[编辑]

^ Brualdi 2010，第74 Theorem 3.2.1页

参考文献[编辑]

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.

[1] Brualdi 2010，第74 Theorem 3.2.1页

[1]