鴿巢原理檢視原始碼討論檢視歷史

鴿巢原理

原圖鏈接

中文名: 抽屜原理 外文名: Pigeonhole principle 別 名: 鴿巢原理、重疊原理、狄利克雷抽屜原理 提出者: 狄利克雷 提出時間: 1834年 適用領域: 組合數學 應用學科: 數學

桌上有十個蘋果，要把這十個蘋果放到九個抽屜里，無論怎樣放，我們會發現至少會有一個抽屜裡面放不少於兩個蘋果。這一現象就是我們所說的「抽屜原理」。 抽屜原理的一般含義為：「如果每個抽屜代表一個集合，每一個蘋果就可以代表一個元素，假如有n+1個元素放到n個集合中去，其中必定有一個集合里至少有兩個元素。」 抽屜原理有時也被稱為鴿巢原理。它是組合數學中一個重要的原理。

原理1： 把多於n個的物體放到n個抽屜里，則至少有一個抽屜里的東西不少於兩件。

證明（反證法）：如果每個抽屜至多只能放進一個物體，那麼物體的總數至多是n×1，而不是題設的n+k(k≥1)，故不可能。

原理2：把多於mn(m乘n)+1（n不為0）個的物體放到n個抽屜里，則至少有一個抽屜里有不少於（m+1）的物體。

證明（反證法）：若每個抽屜至多放進m個物體，那麼n個抽屜至多放進mn個物體，與題設不符，故不可能。

原理3：把無數還多件物體放入n個抽屜，則至少有一個抽屜里有無數個物體。

原理1 、2 、3都是第一抽屜原理的表述。

第二抽屜原理

把（mn－1）個物體放入n個抽屜中，其中必有一個抽屜中至多有（m—1）個物體(例如，將3×5-1=14個物體放入5個抽屜中，則必定有一 個抽屜中的物體數少於等於3-1=2)。

運用抽屜原理的核心是分析清楚問題中，哪個是物件，哪個是抽屜。例如，屬相是有12個，那麼任意37個人中，至少有一個屬相是不少於4個人。這時將屬相看成12個抽屜，則一個抽屜中有 37/12，即3餘1，餘數不考慮，而向上考慮取整數，所以這裡是3+1=4個人，但這裡需要注意的是，前面的餘數1和這裡加上的1是不一樣的。

因此，在問題中，較多的一方就是物件，較少的一方就是抽屜，比如上述問題中的屬相12個，就是對應抽屜，37個人就是對應物件，因為37相對12多。

最差原則

最差原則，即考慮所有可能情況中，最不利於某件事情發生的情況。

例如，有300人到招聘會求職，其中軟件設計有100人，市場營銷有80人，財務管理有70人，人力資源管理有50人。那麼至少有多少人找到工作才能保證一定有70人找的工作專業相同呢？

此時我們考慮的最差情況為：軟件設計、市場營銷和財務管理各錄取69人，人力資源管理的50人全部錄取，則此時再錄取1人就能保證有70人找到的工作專業相同。因此至少需要69*3+50+1=258人。

根據第一抽屜原理之原理2推導：mn+1個人的時候必有m+1個人找到的工作專業相同，所以是要求出mn+1的人數，已知n=3，m+1=70。考慮 到人力資源專業只有50人，得出mn+1=(69*3+50)+1=258人。

一個抽屜里有20件襯衫，其中4件是藍的，7件是灰的，9件是紅的，則應從中隨意取出多少件才能保證有5件是同顏色的？

根據鴿巢原理，n個鴿巢，kn + 1隻鴿子，則至少有一個鴿巢中有k + 1隻鴿子。若根據鴿巢原理的推論直接求解，此時k=4，n=3，則應抽取 3 X 4 + 1 = 13件才能保證有5件同色。其實不然，問題的模型和鴿巢原理不盡相同。在解決該問題時，應該考慮最差的情況，連續抽取過程中抽取出4件藍色的襯衣，即4件藍色，取走後，問題變成有灰色和紅色構成相同顏色的情況，這時，n=2，k + 1 = 5, k = 4. 故 應取 4 + 4 X 2 + 1 = 13件。

問題分析：該情況下鴿巢原理的推論不再適用，由於藍色的襯衫只有4件，而題目中要求有5件是同色的，導致4件藍色襯衫都被抽取出這 一最差情況的存在，所以應該先考慮最差情況，然後在此基礎上再運用鴿巢原理。

證明

（反證法）：若每個抽屜都有不少於m個物體，則總共至少有mn個物體，與題設矛盾，故不可能。

表現形式

把它推廣到一般情形有以下幾種表現形式。

形式一：設把n+1個元素劃分至n個集合中(A1，A2，…，An)，用a1，a2，…，an分別表示這n個集合對應包含的元素個數，則：至少存在 某個集合Ai，其包含元素個數值ai大於或等於2。

證明：（反證法）假設結論不成立，即對每一個ai都有ai<2，則因為ai是整數，應有ai≤1，於是有：

a1+a2+…+an≤1+1+…+1=n<n+1，這與題設矛盾。

所以，至少有一個ai≥2，即必有一個集合中含有兩個或兩個以上的元素。

形式二：設把nm+1個元素劃分至n個集合中(A1，A2，…，An)，用a1，a2，…，an表示這n個集合對應包含的元素個數，則：至少存在某個集合Ai，其包含元素個數值ai大於或等於m+1。

證明：（反證法）假設結論不成立，即對每一個ai都有ai<m+1，則因為ai是整數，應有ai≤m，於是有：

a1+a2+…+an≤m+m+…+m=nm<nm+1，這與題設相矛盾。

所以，至少有存在一個ai≥m+1

知識擴展——高斯函數[x]定義：對任意的實數x，[x]表示「不大於x的最大整數」。例如：[3.5]=3，[2.9]=2，[－2.5]=－3，=7，…… 一般地，我們有：[x]≤x<[x]+1

形式三：設把n個元素分為k個集合A1，A2，…，Ak，用a1，a2，…，ak表示這k個集合里相應的元素個數，需要證明至少存在某個ai大於 或等於[n/k]。

證明：（用反證法）假設結論不成立，即對每一個ai都有ai<[n/k]，於是有：

a1+a2+…+ak<[n/k]+[n/k]+…+[n/k] =k*[n/k]≤k*(n/k)=n

k個[n/k] ∴ a1+a2+…+ak<n 這與題設相矛盾。所以，必有一個集合中元素個數大於或等於[n/k]

形式四：設把q1+q2+…+qn－n+1個元素分為n個集合A1，A2，…，An，用a1，a2，…，an表示這n個集合里相應的元素個數，需要證明至少存在某個i，使得ai大於或等於qi。

證明：（用反證法）假設結論不成立，即對每一個ai都有ai<qi，因為ai為整數，應有ai≤qi－1，

於是有：a1+a2+…+an≤q1+q2+…+qn－n <q1+q2+…+qn－n+1這與題設矛盾。

所以，假設不成立，故必有一個i,在第i個集合中元素個數ai≥qi

形式五：證明：（用反證法）將無窮多個元素分為有限個集合，假設這有限個集合中的元素的個數都是有限個，則有限個有限數相加，所得的數必是有限數，這就與題設產生矛盾，所以，假設不成立，故必有一個集合含有無窮多個元素。（藉由康托的無窮基數可將鴿巢原理推廣到無窮集中。）

一般表述

在上面的第一個結論中，由於一年最多有366天，因此在367人中至少有2人出生在同月同日。這相當於把367個東西放入 366個抽屜，至少有2個東西在同一抽屜里。在第二個結論中，不妨想象將5雙手套分別編號，即號碼為1，2，……，5的手套各有兩隻，同號的兩隻是一雙。任取6隻手套，它們的編號至多有5種，因此其中至少有兩隻的號碼相同。這相當於把6個東西放入5個抽屜，至少有2個東西在同一抽屜里 。

抽屜原理的一種更一般的表述為：

「把多於kn+1個東西任意分放進n個空抽屜（k是正整數），那麼一定有一個抽屜中放進了至少k+1個東西。」

利用上述原理容易證明：「任意7個整數中，至少有3個數的兩兩之差是3的倍數。」因為任一整數除以3時餘數只有0、1、2三種可能，所 以7個整數中至少有3個數除以3所得餘數相同，即它們兩兩之差是3的倍數。

如果問題所討論的對象有無限多個，抽屜原理還有另一種表述：

「把無限多個東西任意分放進n個空抽屜（n是自然數），那麼一定有一個抽屜中放進了無限多個東西。」

用高斯函數來敘述一般形式的抽屜原理的是：將m個元素放入n個抽屜，則在其中一個抽屜里至少會有

[(m-1)/n]+1個元素。

集合論的表述是：設A和B為同基數的有限集，f:A→B為一個映射，則f為單射的充要條件是f為滿射。

抽屜原理的內容簡明樸素，易於接受，它在數學問題中有重要的作用。許多有關存在性的證明都可用它來解決。

這個問題可以用如下方法簡單明了地證出：

在平面上用6個點A、B、C、D、E、F分別代表參加集會的任意6個人。如果兩人以前彼此認識，那麼就在代表他們的兩點間連成一條紅線；否則連一條藍線。考慮A點與其餘各點間的5條連線AB，AC，……，AF，它們的顏色不超過2種。根據抽屜原理可知其中至少有3條連線同色 ，不妨設AB，AC，AD同為紅色。如果BC，BD ，CD 3條連線中有一條（不妨設為BC）也為紅色，那麼三角形ABC即一個紅色三角形，A、B、C代表的3個人以前彼此相識：如果BC、BD、CD 3條連線全為藍色，那麼三角形BCD即一個藍色三角形，B、C、D代表的3個人以前彼此不相 識。不論哪種情形發生，都符合問題的結論。

六人集會問題是組合數學中着名的拉姆塞定理的一個最簡單的特例，這個簡單問題的證明思想可用來得出另外一些深入的結論。這些結論構成了組合數學中的重要內容-----拉姆塞理論。從六人集會問題的證明中，我們又一次看到了抽屜原理的應用。

趣聞

已知n+ 1個互不相同的正整數，它們全都小於或等於2n，證明當中一定有兩個數是互質的。

匈牙利大數學家厄杜斯(PaulErdous,1913 - 1996) 向當年年僅11歲的波薩 (LouisPósa) 提出這個問題，而小波薩思考了不足半分鐘便能給出正確的答案。

波薩是這樣考慮問題：取n個盒子，在第一個盒子我們放1和2，在第二個盒子我們放3和4，第三個盒子是放5和6，依此類推直到第n個盒子放2n-1和2n這兩個數。

如果我們在n個盒子裡隨意抽出n+1個數。我們馬上看到一定有一個盒子是被抽空的。因此在這n+1個數中必有兩個數是連續數，很明顯的 連續數是互質的。因此這問題就解決了！這就是利用了鴿巢原理的核心思想。