抽屜原理(鴿巢原理)

抽屜原理(名詞)

鴿巢原理一般指本詞條

本詞條是多義詞,共2個義項
更多義項 ▼ 收起列表 ▲

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

基本介紹

  • 中文名:抽屜原理
  • 外文名:Pigeonhole principle
  • 別稱:鴿巢原理、重疊原理、狄利克雷抽屜原理
  • 提出者狄利克雷
  • 提出時間:1834年
  • 套用學科數學
  • 適用領域範圍組合數學
原理,第一抽屜原理,第二抽屜原理,常見運用,構造抽屜的方法,最差原則,證明,表現形式,一般表述,趣聞,

原理

第一抽屜原理

原理1: 把多於n+1個的物體放到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]=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個元素。
抽屜原理的內容簡明樸素,易於接受,它在數學問題中有重要的作用。許多有關存在性的證明都可用它來解決。
這個問題可以用如下方法簡單明了地證出:
在平面上用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個數中必有兩個數是連續數,很明顯的連續數是互質的。因此這問題就解決了!這就是利用了鴿巢原理的核心思想。

相關詞條

熱門詞條

聯絡我們