鸽巢原理

<image>

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

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

- 若有$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 \le 1$

所以$a_1+a_2+\cdots+a_n \le 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} <pre> f(i) & i \neq j \\ k & i = j </pre> \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| \ge \left\lceil \frac{m}{n} \right\rceil$

## 更强的形式

设 q1, q2, ..., qn 皆是正整数，现有

$$q_1 + q_2 + \cdots + q_n - n + 1$$

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

- 第1个箱子包含至少q1个物件。
- 第2个箱子包含至少q2个物件。
- 第n个箱子包含至少qn个物件。

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

## 无穷集中的情况

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

## 参见

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

## 外部链接

- 鸽笼原理；谢聪智对鸽巢原理的介绍。
- " 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.