鴿巢原理

鴿巢原理，又名狄利克雷抽屜原理、鴿籠原理。

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

其中一種簡單的表述法為：

• 若有${\displaystyle n}$個籠子和${\displaystyle n+1}$隻鴿子，所有的鴿子都被關在鴿籠裡，那麼至少有一個籠子有至少${\displaystyle 2}$隻鴿子。

另一種為：

• 若有${\displaystyle n}$個籠子和${\displaystyle kn+1}$隻鴿子，所有的鴿子都被關在鴿籠裡，那麼至少有一個籠子有至少${\displaystyle k+1}$隻鴿子。

集合论的表述如下：

• 若${\displaystyle A}$是${\displaystyle n+1}$元集，${\displaystyle B}$是${\displaystyle n}$元集，則不存在從${\displaystyle A}$到${\displaystyle 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个容器中，必有至少一个容器容纳至少${\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}$

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

数学归纳法

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

若${\displaystyle n=1}$，易得原式成立。

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

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

概率方法

将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的单射。

參見

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