抽屜原理也被稱為鴿巢原理，由德國(guó)數(shù)學(xué)家狄利克雷首先發(fā)現(xiàn)，因此又叫狄利克雷原理，是組合數(shù)學(xué)中一個(gè)重要的原理。抽屜原理的一般含義為：如果每個(gè)抽屜代表一個(gè)集合，每一個(gè)蘋果就可以代表一個(gè)元素，假如有n+1或多于n+1個(gè)元素放到n個(gè)集合中去，其中必定至少有一個(gè)集合里有兩個(gè)元素。

原理簡(jiǎn)介

第一抽屜原理

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

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

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

證明（反證法）：若每個(gè)抽屜至多放進(jìn)m個(gè)物體,那么n個(gè)抽屜至多放進(jìn)mn個(gè)物體,與題設(shè)不符，故不可能。

原理3：把無(wú)數(shù)還多件物體放入n個(gè)抽屜，則至少有一個(gè)抽屜里有無(wú)數(shù)個(gè)物體。

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

第二抽屜原理

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

常見(jiàn)運(yùn)用

構(gòu)造抽屜的方法

運(yùn)用抽屜原理的核心是分析清楚問(wèn)題中，哪個(gè)是物件，哪個(gè)是抽屜。例如，屬相是有12個(gè)，那么任意37個(gè)人中，至少有一個(gè)屬相是不少于4個(gè)人。這時(shí)將屬相看成12個(gè)抽屜，則一個(gè)抽屜中有?37/12，即3余1，余數(shù)不考慮，而向上考慮取整數(shù)，所以這里是3+1=4個(gè)人，但這里需要注意的是，前面的余數(shù)1和這里加上的1是不一樣的。

因此，在問(wèn)題中，較多的一方就是物件，較少的一方就是抽屜，比如上述問(wèn)題中的屬相12個(gè)，就是對(duì)應(yīng)抽屜，37個(gè)人就是對(duì)應(yīng)物件，因?yàn)?7相對(duì)12多。

最差原則

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

例如，有300人到招聘會(huì)求職，其中軟件設(shè)計(jì)有100人，市場(chǎng)營(yíng)銷有80人，財(cái)務(wù)管理有70人，人力資源管理有50人。那么至少有多少人找到工作才能保證一定有70人找的工作專業(yè)相同呢？

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

根據(jù)第一抽屜原理之原理2推導(dǎo)：mn+1個(gè)人的時(shí)候必有m+1個(gè)人找到的工作專業(yè)相同，所以是要求出mn+1的人數(shù)，已知n=3，m+1=70?？紤]到人力資源專業(yè)只有50人，得出mn+1= - 69*3+50+1=258人。

一個(gè)抽屜里有20件襯衫，其中4件是藍(lán)的，7件是灰的，9件是紅的，則應(yīng)從中隨意取出多少件才能保證有5件是同顏色的？

根據(jù)鴿巢原理，n個(gè)鴿巢，kn?+?1只鴿子，則至少有一個(gè)鴿巢中有k?+?1只鴿子。若根據(jù)鴿巢原理的推論直接求解，此時(shí)k=4，n=3，則應(yīng)抽取?3?X?4?+?1?=?13件才能保證有5件同色。其實(shí)不然，問(wèn)題的模型和鴿巢原理不盡相同。在解決該問(wèn)題時(shí)，應(yīng)該考慮最差的情況，連續(xù)抽取過(guò)程中抽取出4件藍(lán)色的襯衣，即4件藍(lán)色，取走后，問(wèn)題變成有灰色和紅色構(gòu)成相同顏色的情況，這時(shí)，n=2，k?+?1?=?5,?k?=?4.?故應(yīng)取?4?+?4?X?2?+?1?=?13件。

問(wèn)題分析：該情況下鴿巢原理的推論不再適用，由于藍(lán)色的襯衫只有4件，而題目中要求有5件是同色的，導(dǎo)致4件藍(lán)色襯衫都被抽取出這一最差情況的存在，所以應(yīng)該先考慮最差情況，然后在此基礎(chǔ)上再運(yùn)用鴿巢原理。

證明

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

表現(xiàn)形式

把它推廣到一般情形有以下幾種表現(xiàn)形式。

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

證明：（反證法）假設(shè)結(jié)論不成立，即對(duì)每一個(gè)ai都有ai<2，則因?yàn)閍i是整數(shù)，應(yīng)有ai≤1，于是有：

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

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

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

證明：（反證法）假設(shè)結(jié)論不成立，即對(duì)每一個(gè)ai都有ai<m+1，則因?yàn)閍i是整數(shù)，應(yīng)有ai≤m，于是有：

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

所以，至少有存在一個(gè)ai≥m+1

知識(shí)擴(kuò)展——高斯函數(shù)[x]定義：對(duì)任意的實(shí)數(shù)x，[x]表示“不大于x的最大整數(shù)”。例如：[3.5]=3，[2.9]=2，[－2.5]=－3，[7]=7，……一般地，我們有：[x]≤x<[x]+1

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

證明：（用反證法）假設(shè)結(jié)論不成立，即對(duì)每一個(gè)ai都有ai<[n/k]，于是有：

a1+a2+…+ak<[n/k]+[n/k]+…+[n/k]?=k*[n/k]≤k* - n/k=n

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

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

證明：（用反證法）假設(shè)結(jié)論不成立，即對(duì)每一個(gè)ai都有ai<qi，因?yàn)閍i為整數(shù)，應(yīng)有ai≤qi－1，

于是有：a1+a2+…+an≤q1+q2+…+qn－n?<q1+q2+…+qn－n+1這與題設(shè)矛盾。

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

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

一般表述

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

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

“把多于kn+1個(gè)東西任意分放進(jìn)n個(gè)空抽屜（k是正整數(shù)），那么一定有一個(gè)抽屜中放進(jìn)了至少k+1個(gè)東西?！?/p>

利用上述原理容易證明：“任意7個(gè)整數(shù)中，至少有3個(gè)數(shù)的兩兩之差是3的倍數(shù)?！币?yàn)槿我徽麛?shù)除以3時(shí)余數(shù)只有0、1、2三種可能，所以7個(gè)整數(shù)中至少有3個(gè)數(shù)除以3所得余數(shù)相同，即它們兩兩之差是3的倍數(shù)。

如果問(wèn)題所討論的對(duì)象有無(wú)限多個(gè)，抽屜原理還有另一種表述：

“把無(wú)限多個(gè)東西任意分放進(jìn)n個(gè)空抽屜（n是自然數(shù)），那么一定有一個(gè)抽屜中放進(jìn)了無(wú)限多個(gè)東西?！?/p>

用高斯函數(shù)來(lái)敘述一般形式的抽屜原理的是：將m個(gè)元素放入n個(gè)抽屜，則在其中一個(gè)抽屜里至少會(huì)有

[ - m-1]+1個(gè)元素。

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

抽屜原理的內(nèi)容簡(jiǎn)明樸素，易于接受，它在數(shù)學(xué)問(wèn)題中有重要的作用。許多有關(guān)存在性的證明都可用它來(lái)解決。

這個(gè)問(wèn)題可以用如下方法簡(jiǎn)單明了地證出：

在平面上用6個(gè)點(diǎn)A、B、C、D、E、F分別代表參加集會(huì)的任意6個(gè)人。如果兩人以前彼此認(rèn)識(shí)，那么就在代表他們的兩點(diǎn)間連成一條紅線；否則連一條藍(lán)線?？紤]A點(diǎn)與其余各點(diǎn)間的5條連線AB，AC，…，AF，它們的顏色不超過(guò)2種。根據(jù)抽屜原理可知其中至少有3條連線同色，不妨設(shè)AB，AC，AD同為紅色。如果BC，BD?，CD?3條連線中有一條（不妨設(shè)為BC）也為紅色，那么三角形ABC即一個(gè)紅色三角形，A、B、C代表的3個(gè)人以前彼此相識(shí)：如果BC、BD、CD?3條連線全為藍(lán)色，那么三角形BCD即一個(gè)藍(lán)色三角形，B、C、D代表的3個(gè)人以前彼此不相識(shí)。不論哪種情形發(fā)生，都符合問(wèn)題的結(jié)論。

六人集會(huì)問(wèn)題是組合數(shù)學(xué)中著名的拉姆塞定理的一個(gè)最簡(jiǎn)單的特例，這個(gè)簡(jiǎn)單問(wèn)題的證明思想可用來(lái)得出另外一些深入的結(jié)論。這些結(jié)論構(gòu)成了組合數(shù)學(xué)中的重要內(nèi)容—–拉姆塞理論。從六人集會(huì)問(wèn)題的證明中，我們又一次看到了抽屜原理的應(yīng)用。

定理定義

抽屜原理又稱鴿巢原理，它是德國(guó)數(shù)學(xué)家狄利克雷首先明確的提出來(lái)并用以證明一些數(shù)論中的問(wèn)題，因此，也稱為狄利克雷原則。它是組臺(tái)數(shù)學(xué)中一個(gè)重要的原理。是一個(gè)及其初等而有應(yīng)用廣泛的數(shù)學(xué)原理。

桌上有4個(gè)蘋果，要把這4個(gè)蘋果放到3個(gè)抽屜里，無(wú)論怎樣放，會(huì)發(fā)現(xiàn)至少會(huì)有一個(gè)抽屜里面至少放2個(gè)蘋果，這一現(xiàn)象就是所說(shuō)的抽屜原理。抽屜原理的一般含義為：如果每個(gè)抽屜代表一個(gè)集合，每一個(gè)蘋果就可以代表一個(gè)元素，假如有n+1或多于n+1個(gè)元素放到n個(gè)集合中去，其中必定至少有一個(gè)集合里有2個(gè)元素。抽屜原理有時(shí)也被稱為鴿巢原理（如果有5個(gè)鴿子籠，養(yǎng)鴿人養(yǎng)了6只鴿子，那么當(dāng)鴿子飛回籠中后，至少有一個(gè)籠子中裝有至少2只鴿子）。

驗(yàn)證推導(dǎo)

第一抽屜原理：

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

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

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

證明（反證法）：若每個(gè)抽屜至多放進(jìn)m個(gè)物體，那么n個(gè)抽屜至多放進(jìn)mn個(gè)物體，與題設(shè)不符，故不可能。

原理3：把無(wú)窮多件物體放入n個(gè)抽屜，則至少有一個(gè)抽屜里?有無(wú)窮個(gè)物體。

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

第二抽屜原理：

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

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

從六人集會(huì)問(wèn)題的證明中看出抽屜原理的應(yīng)用：

在平面上用6個(gè)點(diǎn)A、B、C、D、E、F分別代表參加集會(huì)的任意6個(gè)人。如果兩人以前彼此認(rèn)識(shí)，那么就在代表他們的兩點(diǎn)間連成一條紅線；否則連一條藍(lán)線?？紤]A點(diǎn)與其余各點(diǎn)間的5條連線AB，AC，…，AF，它們的顏色不超過(guò)2種。

根據(jù)抽屜原理可知其中至少有3條連線同色，不妨設(shè)AB，AC，AD同為紅色。如果BC，BD，CD3條連線中有一條（不妨設(shè)為BC）也為紅色，那么三角形ABC即一個(gè)紅色三角形，A、B、C代表的3個(gè)人以前彼此相識(shí)：如果BC、BD、CD3條連線全為藍(lán)色，那么三角形BCD即一個(gè)藍(lán)色三角形，B、C、D代表的3個(gè)人以前彼此不相識(shí)。不論哪種情形發(fā)生，都符合問(wèn)題的結(jié)論。

六人集會(huì)問(wèn)題是組合數(shù)學(xué)中著名的拉姆塞定理的一個(gè)最簡(jiǎn)單的特例，這個(gè)簡(jiǎn)單問(wèn)題的證明思想可用來(lái)得出另外一些深入的結(jié)論。

定理推廣

把它推廣到一般情形有以下幾種表現(xiàn)形式：

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

證明：（反證法）假設(shè)結(jié)論不成立，即對(duì)每一個(gè)ai都有ai<2，則因?yàn)閍i是整數(shù)，應(yīng)有ai≤1，于是有：

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

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

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

證明：（反證法）假設(shè)結(jié)論不成立，即對(duì)每一個(gè)ai都有ai<m+1，則因?yàn)閍i是整數(shù)，應(yīng)有ai≤m，于是有：

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

所以，至少有存在一個(gè)ai≥m+1

知識(shí)擴(kuò)展——高斯函數(shù)[x]定義：對(duì)任意的實(shí)數(shù)x，[x]表示“不大于x的最大整數(shù)”。例如：[3.5]=3，[2.9]=2，[－2.5]=－3，[7]=7，……一般地，我們有：[x]≤x<[x]+1

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

證明：（用反證法）假設(shè)結(jié)論不成立，即對(duì)每一個(gè)ai都有ai<[n/k]，于是有：

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

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

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

證明：（用反證法）假設(shè)結(jié)論不成立，即對(duì)每一個(gè)ai都有ai<qi，因?yàn)閍i為整數(shù)，應(yīng)有ai≤qi－1，

于是有：a1+a2+…+an≤q1+q2+…+qn－n<q1+q2+…+qn－n+1這與題設(shè)矛盾。

所以，假設(shè)不成立，故必有一個(gè)i，在第i個(gè)集合中元素個(gè)數(shù)ai≥qi

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

發(fā)展簡(jiǎn)史

抽屜原理又叫鴿籠原理，它由德國(guó)數(shù)學(xué)家狄利克雷 - Dirichlet1805-1859首先發(fā)現(xiàn)，因此又叫狄利克雷原理。狄利克雷在研究數(shù)論的問(wèn)題時(shí)最早很巧妙運(yùn)用抽屜原理去解決問(wèn)題。后來(lái)德國(guó)數(shù)學(xué)家閔可夫斯基 - Minkowski，1864-1909也運(yùn)用這原理得到一些結(jié)果。到了20世紀(jì)初期杜爾 - A.Thue1863-1922在不知道狄利克雷和閔可夫斯基的工作情況下，很機(jī)巧地利用鴿籠原理來(lái)解決不定方程的有理數(shù)解的問(wèn)題有12篇論文是用到這個(gè)原理。后來(lái)西根 - CLSiegel利用杜爾的結(jié)果發(fā)現(xiàn)了現(xiàn)在稱為西根引理的東西這引理 - Lemma是在研究超越數(shù)時(shí)最基本必用的工具。

趣聞

已知n+?1個(gè)互不相同的正整數(shù)，它們?nèi)夹∮诨虻扔?n，證明當(dāng)中一定有兩個(gè)數(shù)是互質(zhì)的。

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

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

如果我們?cè)趎個(gè)盒子里隨意抽出n+1個(gè)數(shù)。我們馬上看到一定有一個(gè)盒子是被抽空的。因此在這n+1個(gè)數(shù)中必有兩個(gè)數(shù)是連續(xù)數(shù)，很明顯的連續(xù)數(shù)是互質(zhì)的。因此這問(wèn)題就解決了！這就是利用了鴿巢原理的核心思想。