鸽巢原理

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

• 比如：北京至少有两个人头发数一样多。
  • 证明：常人的头发数目在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个容器中，必有至少一个容器容纳至少${\displaystyle \left\lceil {\frac {n}{m}}\right\rceil }$ 个对象。

反证法

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

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

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

所以${\displaystyle a_{i}\leq 1}$ 

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

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

概率方法

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

设 q₁, q₂, ..., q_n 皆是正整数，现有

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

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

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

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

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

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

• Grimaldi, Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. 4th edn. 1998. 永久失效链接]

• 鸽笼原理 （页面存档备份，存于互联网档案馆）；谢聪智对鸽巢原理的介绍。
• "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页 harvnb error: no target: CITEREFBrualdi2010 (help)