鴿巢原理

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

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

參見

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

参考资料

1. Brualdi 2010，第74 Theorem 3.2.1頁 harvnb模板錯誤: 無指向目標: CITEREFBrualdi2010 (幫助)

参考文献

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