鴿巢原理
维基百科，自由的百科全书
鴿巢原理，又名狄利克雷抽屜原理、鴿籠原理。
其中一種簡單的表述法為：
- 若有n個籠子和n+1隻鴿子，所有的鴿子都被關在鴿籠裡，那麼至少有一個籠子有至少2隻鴿子。
或者這麼說：
- 若有n個籠子和kn+1隻鴿子，所有的鴿子都被關在鴿籠裡，那麼至少有一個籠子有至少k+1隻鴿子。
拉姆齐定理是此原理的推廣。
目录 |
[编辑] 例子
雖然鴿巢原理看起來很容易理解.但有時使用鴿巢原理會得到一些有趣的結論.比如:北京至少有兩個人頭髮數一樣多.證明:常人的頭髮數在15萬左右.可以假定沒有人有超過100萬根頭髮.但北京人口大於100萬.如果我們讓每一個鴿巢對應一個頭髮數字,鴿子對應於人.那就變成了有大於100萬隻鴿子要進到至多100萬個巢中.所以,結論很明顯. 但实际上，这个结论不对。原因是此推导建立在这样一个假设上：如果北京有15萬人，那么每个人的头发数目都一定不同。事实显然不是这样。
另一個例子是: 盒子裡有10只黑襪子,12只藍襪子,你需要拿一對同色的出來.假設你總共只能拿一次,而且拿的時候還看不到.那你應該拿幾隻出來,才能保證有一雙同色的呢? 可能有人會脫口而出"13只!" 其實3只就可以了. 因為顏色只有兩種(鴿巢只有兩個),而三隻襪子(三隻鴿子),結論明顯了...
更不直觀一點的例子:有n個人(至少2人)互相握手(隨意找人握),必有兩人握手次數相同.這裡,鴿巢對應於握手次數,鴿子對應於人.每個人都可以握[0,n-1]次(但0和n-1不能同時存在,因為如果一個人不和任何人握手,那就不會存在一個和所有其他人都握過手的人).所以鴿巢是n-1個.但有n個人(n只鴿子),得證啦...
其實,鴿巢原理經常在計算機領域得到真正的應用.比如,哈希表的重複問題(衝突)是不可避免的,因為Keys的數目總是比Indices的數目多.不管是多麼高明的算法都不可能解決這個問題. 這個原理還證明了,任何無損壓縮算法在把一個文件變小的同時,必有其他文件的增大來輔助.否則某些信息必然會丟失.
[编辑] 推广
一种表达是这样的:如果要把n个物件分配到m个容器中,必有至少一个容器容纳至少⌈n / m⌉个物件.(⌈x⌉大于等于x的最小的整数)
[编辑] 无穷集中的情况
籍由康托的无穷基数可将鸽巢原理推广到无穷集中.
[编辑] References
- 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.
