鴿巢原理

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