抽屜原理:數學原理-中文百科頻道

原理簡介

第一抽屜原理

原理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，則應抽取3X4+1=13件才能保證有5件同色。其實不然，問題的模型和鴿巢原理不盡相同。在解決該問題時，應該考慮最差的情況，連續抽取過程中抽取出4件藍色的襯衣，即4件藍色，取走後，問題變成有灰色和紅色構成相同顔色的情況，這時，n=2，k+1=5,k=4.故應取4+4X2+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

形式三：設把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

形式四：設把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個元素。

集合論的表述是：設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，CD3條連線中有一條（不妨設為BC）也為紅色，那麼三角形ABC即一個紅色三角形，A、B、C代表的3個人以前彼此相識：如果BC、BD、CD3條連線全為藍色，那麼三角形BCD即一個藍色三角形，B、C、D代表的3個人以前彼此不相識。不論哪種情形發生，都符合問題的結論。

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