共找到3條詞條名為抽屜原理的結果 展開
- 1834年狄利克雷提出的原理
- 2012年常庚哲創作的書籍
- 鴿舍原理
抽屜原理
1834年狄利克雷提出的原理
桌上有十個蘋果，要把這十個蘋果放到九個抽屜里，無論怎樣放，我們會發現至少會有一個抽屜裡面放兩個蘋果。這一現象就是我們所說的“抽屜原理”。抽屜原理的一般含義為：“如果每個抽屜代表一個集合，每一個蘋果就可以代表一個元素，假如有n+1個元素放到n個集合中去，其中必定有一個集合里至少有兩個元素。”抽屜原理有時也被稱為鴿巢原理。它是組合數學中一個重要的原理。
：+抽屜，則抽屜件。
抽屜原理
：把多於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
所以，至少有一個ai≥2，即必有一個集合中含有兩個或兩個以上的元素。
形式二：設把nm+1個元素劃分至n個集合中(A1，A2，…，An)，用a1，a2，…，an表示這n個集合對應包含的元素個數，則：至少存在某個集合Ai，其包含元素個數值ai大於或等於m+1。
證明：（反證法）假設結論不成立，即對每一個ai都有ai
a1+a2+…+an≤m+m+…+m=nm
所以，至少有存在一個ai≥m+1
知識擴展——高斯函數[x]定義：對任意的實數x，[x]表示“不大於x的最大整數”。例如：[3.5]=3，[2.9]=2，[－2.5]=－3，[7]=7，……一般地，我們有：[x]≤x<[x]+1
證明：（用反證法）假設結論不成立，即對每一個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
形式四：設把q1+q2+…+qn－n+1個元素分
為n個集合A1，A2，…，An，用a1，a2，…，an表示這n個集合里相應的元素個數，需要證明至少存在某個i，使得ai大於或等於qi。
抽屜原理
證明：（用反證法）假設結論不成立，即對每一個ai都有ai
於是有：a1+a2+…+an≤q1+q2+…+qn－n
所以，假設不成立，故必有一個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個數中必有兩個數是連續數，很明顯的連續數是互質的。因此這問題就解決了！這就是利用了鴿巢原理的核心思想。
基本信息
- 中文名
- 抽屜原理
- 外文名
- Pigeonhole principle
- 別名
- 鴿巢原理、重疊原理、狄利克雷抽屜原理
- 提出時間
- 1834年
- 提出者
- 狄利克雷
- 術語類別
- 數學術語
- 適用領域範圍
- 組合數學
目錄