鴿巢原理

維基百科,自由的百科全書
(重定向自鴿籠原理
跳轉到: 導覽搜尋
10隻鴿子放進9個鴿籠,那麼一定有一個鴿籠放進了至少兩隻鴿子。

鴿巢原理,又名狄利克雷抽屜原理鴿籠原理

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

  • 若有n個籠子和n+1隻鴿子,所有的鴿子都被關在鴿籠裡,那麼至少有一個籠子有至少2隻鴿子

另一種為:

  • 若有n個籠子和kn+1隻鴿子,所有的鴿子都被關在鴿籠裡,那麼至少有一個籠子有至少k+1隻鴿子

拉姆齊定理是此原理的推廣。

例子[編輯]

雖然鴿巢原理看起來很容易理解,但有時使用鴿巢原理會得到一些有趣的結論:

  • 比如:北京至少有兩個人頭髮數一樣多。
    • 證明:常人的頭髮數在15萬左右,可以假定沒有人有超過100萬根頭髮,但北京人口大於100萬。如果我們讓每一個鴿巢對應一個頭髮數字,鴿子對應於人,那就變成了有大於100萬隻鴿子要進到至多100萬個巢中。所以,可以得到「北京至少有兩個人頭髮數一樣多」的結論。

另一個例子:

  • 盒子裡有10隻黑襪子、12隻藍襪子,你需要拿一對同色的出來。假設你總共只能拿一次,只要3隻就可以拿到相同顏色的襪子,因為顏色只有兩種(鴿巢只有兩個),而三隻襪子(三隻鴿子),從而得到「拿3隻襪子出來,就能保證有一雙同色」的結論。

更不直觀一點的例子:

  • 有n個人(至少2人)互相握手(隨意找人握),必有兩人握手次數相同。
    • 這裡,鴿巢對應於握手次數,鴿子對應於人,每個人都可以握[0,n-1]次(但0和n-1不能同時存在,因為如果一個人不和任何人握手,那就不會存在一個和所有其他人都握過手的人),所以鴿巢是n-1個。但有n個人(n隻鴿子),因此証明了命題正確。

鴿巢原理經常在計算機領域得到真正的應用。比如:哈希表的重複問題(衝突)是不可避免的,因為Keys的數目總是比Indices的數目多,不管是多麼高明的演算法都不可能解決這個問題。這個原理,還證明任何無損壓縮演算法,在把一個文件變小的同時,一定有其他文件增大來輔助,否則某些信息必然會丟失。

推廣[編輯]

一種表達是這樣的:如果要把n個物件分配到m個容器中,必有至少一個容器容納至少⌈n / m⌉個物件。(⌈x⌉大於等於x的最小的整數)

數學證明[編輯]

設把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{Z}

所以 a_i \le 1

所以 a_1+a_2+\cdots+a_n \le 1+1+\cdots+1 = n < n+1

這與題設矛盾,因此結論得證。

無窮集中的情況[編輯]

藉由康托的無窮基數可將鴿巢原理推廣到無窮集中。

來源[編輯]

  • 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.
  • 抽屜原理

外部連結[編輯]