鸽巢原理

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

10只鸽子放进9个鸽笼，那么一定有一个鸽笼放进了至少两只鸽子。

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

• 若有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$

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

数学归纳法

证明：若存在一个从集合$\{1\leq x\leq n|x\in \mathbb {N} \}$到集合$\{1\leq x\leq p|x\in \mathbb {N} \}$的单射$f$，那么$n\leq p$。

若$n=1$，易得原式成立。

若$n>1$，归纳假设存在$p$，有从集合$\{1\leq x\leq n-1|x\in \mathbb {N} \}$到集合$\{1\leq x\leq p|x\in \mathbb {N} \}$的单射,$n-1\leq p$。 若$f:\{1\leq x\leq n|x\in \mathbb {N} \}\rightarrow \{1\leq x\leq p|x\in \mathbb {N} \}$ 如果$p$在映射$f$下没有原像或$f(n)=p$,那么$f$是一个从 $\{1\leq x\leq n|x\in \mathbb {N} \}$到$\{1\leq x\leq p|x\in \mathbb {N} \}$的单射，所以 $n-1\leq p-1$，即$n\leq p$。

如果$p$在映射$f$下有原像，那么我们记$p$在映射$f$下的原像为$j$且$n$在映射$f$得到的像为$k$,可以得到映射: $\{1\leq x\leq n-1|x\in \mathbb {N} \}\rightarrow \{1\leq x\leq p-1|x\in \mathbb {N} \}$ $i\rightarrow {\begin{cases}f(i)&i\neq j\\k&i=j\end{cases}}$ 是一个单射所以$n-1\leq p-1$，即$n\leq p$。

概率方法

将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₁, q₂, ..., q_n 皆是正整数，现有

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

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

• 第1个箱子包含至少q₁个物件；
• 第2个箱子包含至少q₂个物件；
• ......
• 第n个箱子包含至少q_n个物件。

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

无穷集中的情况

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

参见

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

参考资料

参考文献

• 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.