抽屜原理（Pigeonhole principle）也稱鴿巢原理、重疊原理或狄利克雷抽屜原理，是一個初等且應用廣泛的數學原理，同時也是組合數學中一個重要的原理。抽屜原理的一般含義為：如果每個抽屜代表一個集合，每一個蘋果就可以代表一個元素，假如有n+1個元素放到n個集合中去，其中必定有一個集合里至少有兩個元素。抽屜原理要解決的是存在性問題，即在具體的組合問題中，要計算某些特定問題求解的方案數。
該原理是1834年狄利克雷提出的。1846年，他使用抽屜原理闡明代數數域中單位數的阿壩爾群結構。1930年，英國邏輯學家弗蘭克·P·拉姆（F.P.Ramsey）將這個簡單原理作了深刻推廣，從而獲得拉姆齊定理，該定理也被稱為廣義抽屜原理。
抽屜原理通常用在整除問題、面積問題以及染色問題上。研究與整除有關的問題時，?常用剩余類作為抽屜；在面積問題上例如已知在邊長為1的等邊三角形內(包括邊界)有任意10個點。證明至少有兩個點之間的距離不大于1/3；染色問題如例如：將平面上每點都任意地染上黑白兩色之一。求證：?一定存在一個邊長為1或3的正三角形，它的三個頂點同色。
定義
抽屜原理又稱鴿巢原理或重疊原理，是組合數學中基本原理之一，其定義為一般情況下，把n+1或多于n+1個蘋果放到n個抽屜里，其中必定至少有一個抽屜里至少有兩個蘋果。人們稱這種現象為抽屜原理。例如桌上有十個蘋果，要把這十個蘋果放到九個抽屜里，不限制每個抽屜中放置的蘋果個數，?如有的抽屜可以放一個，有的可以放兩個，有的可以放五個，但最終會發現至少可以找到一個抽屜里面至少放兩個蘋果。該原理要解決的是存在性問題，即在具體的組合問題中，要計算某些特定問題求解的方案數，其前提就是要知道這些方案的存在性。
第一抽屜原理
第二抽屜原理
把（錳1）個物體放入n個抽屜，其中必有一個抽屜中至多有（m-1）個物體。例如若把3個蘋果放入4個抽屜中，則必然有一個抽屜空著。
簡史
1834年，德國數學家狄利克雷提出抽屜原理，1846年，他使用抽屜原理闡明代數數域中單位數的阿壩爾群結構。1930年，英國邏輯學家弗蘭克·P·拉姆齊將這個簡單原理作了深刻推廣，從而獲得拉姆齊定理，該定理也被稱為廣義抽屜原理。
1947年，匈牙利數學競賽試題出現了關于抽屜原理的題：證明任意6個人的集會上，總有3人互相認識或互相不認識。1959年，《美國數學月刊》又進一步提出：任意18個人的集會上，一定有4人或互相認識，或互相不認識。
抽屜原理也可以用集合論，高斯函數來表示，集合論是由格奧爾格·康托爾在19世紀提出的，他把全體自然數看作一個集合，并且在1873年證明了實數集的勢大于自然數集。集合論提出伊始，遭到很多數學家的反對，直到20世紀初才獲得世界公認。高斯在19世紀初首次清晰地闡述了復數和復變量函數的研究，并且將高斯函數引入到概率統計領域。
證明
原理1
反證法
將n+1個物品放入n?個抽屜，則至少有一個抽屜中的物品數不少于兩個。
證明（反證法）：將抽屜編號為：1，2，?…?，n，設第?i個抽屜放有qi個物品，則q?+q?+…qn=n+1。?但若定理結論不成立，即qi≤1，即有q?+q2+…+qn≤n，從而有n+1=q?+q?+…+qn≤n矛盾。從而原定理成立。
枚舉法
例如，證明把4支鉛筆放進3個筆筒中，不管怎么放，總有一個筆筒里至少有2支鉛筆。
證明：枚舉出4種可能的擺法，即(4，0，0)、(3，1，0)、(2，2，0)、(2，1，1)，比較發現在每一種擺法中最多的那個筆筒，?鉛筆的支數分別是4、3、2，根據此枚舉結果，得出數學結論是："把4支鉛筆放進3個筆筒中，不管怎么放，總有一個筆筒里至少有2支鉛筆。”
原理2
把多于mn(m乘n)+1（n不為0）個的物體放到n個抽屜里，則至少有一個抽屜里有不少于（m+1）的物體。
證明（反證法）：假定這n個抽屜中，每一個抽屜內的物品都不到（m+1）件，即每個抽屜里的物品都不多于m件，這樣，n個抽屜中可放物品的總數就不會超過m×n件。這與多于m×?n件物品的假設相矛盾。這說明一開始的假定不能成立。所以至少有一個抽屜中物品的件數不少于m+1。
枚舉法：例如，把7本書放進3個抽屜，不管怎么放，總有一個抽屜里至少放進3本書。
證明：枚舉法一一擺出，即（1）7，0，0；（2）6，1，0；（3）5，2，0，…?；（x）3，2，2。可舉出的例子太多，重要的是第一種和最后一種擺法。得出結論是“總有一個抽屜里至少放進3本書”。
原理3
把無窮多個物體按任意方式放入n個抽屜，則至少有一個抽屜里有無窮多個物體證明同原理2(略)?。
原理4
把（mn-1）個物體放入n個抽屜中，其中必有一個抽屜中至多有?(m-1)?個物體。
證明(反證法)：若每個抽屜都有不少于m個物體，則總共至少有mn個物體，與題設矛盾，故不可能。
集合形式
抽屜原理可以推廣到以下幾種表現形式：
形式一
n+1個元素分為n個集合，那么必有一個集合中含有兩個或兩個以上的元素。
證明：設把n+1個元素分為n個集合A?，A?，…，An，用?a?，a?，…，an表示這n個集合里相應的元素個數，需要證明至少存在某個ai大于或等于2。
(用反證法)假設結論不成立，即對每一個ai，都有ai<2，則因為ai是整數，應有ai≤1，于是有：
a1+a?+…+an≤1+1+…+1=n 這與題設矛盾。所以，至少有一個ai≥2，即必有一個集合中含有兩個或兩個以上的元素。 nm+1個元素分為n個集合中，那么至少有一個集合中存在m+l個元素。 證明：設把nm+1個元素分為n個集合A?，A?，…，An，用a1+a?…?表示這n個集合里相應的元素個數，需要證明至少存在某個ai大于或等于m+1。 (用反證法)假設結論不成立，即對每一個ai，都有ai a?+a?+?…+an≤m+m+?…+m=nm n個m?這與題設相矛盾。所以，至少存在一個ai≥m+1。 n個元素分為k個集合中，其中必有一個集合中元素個數大于或等于[n/k]。 證明：設把n個元素分為k個集合a?，a?，…，ak，表示這k個集合里相應的元素個數，需要證明至少存在某個ai，大于或等于?[n/k]。? (用反證法)假設結論不成立，即對每一個ai都有ai<[n/k], ?于是有： a?+a?+?…+ak<[n/k]+[n/k]+?…+[n/k]=k[n/k]=n 因為a?+a?+…+ak 形式四?q?+q?+…+qn-n+1個元素分為n個集合，那么必有一個i（1 證明：設把q?+q?+…+qn-n+1個元素分為n個集合A?，A?，…，An，用a?+a?+…+an表示這n個集合里相應的元素個數，需要證明至少存在某個i，使得ai大于或等于qi。 (用反證法)假設結論不成立，即對每一個ai都有ai a?+a?+…+an≤q?+q?+…+qn-n 這與題設矛盾。所以，假設不成立，故必有一個i，在第i個集合中元素個數ai≥qi。 設有無窮多個元素按任一確定的方式分成有限個集合，那么至少有一個集合含有無窮多個元素（借由康托的無窮基數可將鴿巢原理推廣到無窮集中）。 證明：（用反證法）將無窮多個元素分為有限個集合，假設這有限個集合中的元素的個數都是有限個，則有限個有限數相加，所得的數必是有限數，這就與題設產生矛盾，所以，假設不成立，故必有一個集合含有無窮多個元素。 將m個元素放入n個抽屜，則在其中一個抽屜里至少會有??個元素。當時，即為形式一（n+1個元素分為n個集合，那么必有一個集合中含有兩個或兩個以上的元素）；當?時，即為形式二（nm+1個元素分為n個集合中，那么至少有一個集合中存在m+l個元素）。所以，形式一是形式二的特例。 設A，B為兩個有限的集合，若，則從A到B的任意函數，必有，且a1≠a2，使得。 用集合論表述為：若有非空有限集合A，，π是A的任意劃分，且，則至少有一個劃分塊的元素個數不少于2。 拉姆齊定理也稱廣義的抽屜原理，其定義為n個點散布在紙上，每個點都用紅色或藍色的直線連接到每個其他點，n必須大于等于6，才能確保紙上出現藍色三角形或紅色三角形。例如：在任意等于或超過6個人的集會上，至少有3個人以前彼此相識，或者有三個人以前彼此不相識。但是如果人數少于6人，則這種情況就不一定出現。 證明：如下圖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個人以前彼此不相識。不論哪種情形發生，都符合問題的結論。需要補充兩點：如果只有5個點或更少，拉姆齊定理不一定成立。如下圖2所示的五邊形和它中間的五角星是兩個顏色，那這圖中就沒有全色三角形。?如果多于6個點，當然拉姆齊定理一樣成立。 運用抽屜原理的核心是分析清楚問題中哪個是物件，哪個是抽屜。例如，屬相有12個，那么任意37個人中，有幾個人屬相相同呢。這時將屬相看成12個抽屜，則一個抽屜中有37/12個，即3余1，余數需要考慮，因此向上取整時需加1，所以至少有一個屬相是不少于4個人。 因此，在問題中，較多的一方就是物件，較少的一方就是抽屜，比如上述問題中的屬相12個，就是對應抽屜，37個人就是對應物件，因為37相對12多。 應用抽屜原理解決問題時，通常需要先考慮最不利情況，再在此基礎上運用鴿巢原理。例如在特定情況下（如藍色的襯衫只有4件，而題目要求有5件同色時），由于4件藍色襯衫都被抽取出這一最差情況的存在，鴿巢原理的推論不再直接適用，需先考慮該最差情況。 再如：黑色、白色、黃色的筷子各有8根，混雜地放在一起，黑暗中想從這些筷子中取出顏色不同的2雙筷子（每雙筷子兩根的顏色應一樣），問至少要取多少根才能保證達到要求。 解：由于有三種顏色的筷子，而且混雜在一起，我們在黑暗中取筷子時無法分辨出筷子的顏色，這樣如果取的筷子數目不多于8根的話，有可能取出的是同一顏色，這是最不利的情況。因此要想保證取出顏色不同的2雙筷子，取出的筷子數必須超過8根為了保證達到要求，我們從最不利的情況出發，假設開始取出的筷子8根都是同一顏色，這時問題就變成了后面怎樣才能使所取的筷子中保證有兩根的顏色相同這時，剩下的顏色只有兩種，把兩種顏色看作兩個抽屜，把筷子當作蘋果，根據抽屜原理，?只需再取出3根筷子就能保證有兩根的顏色相同。總之，在最不利的情況下，只要取出8+3=11根筷子，就能保證有顏色不同的2雙筷子，所以，至少要取11根筷子才能保證達到要求。 把所有整數按照除以某個自然數m的余數分為m類，叫做m的剩余類或同余類，用，，，?…?，[m-1]表示。每一個類含有無窮多個數。例如：中含有1，m+1，2m+1，3m+1，…。在研究與整除有關的問題時，?常用剩余類作為抽屜。根據抽屜原理，可以證明：任意n+1個自然數中，總有兩個自然數的差是n?的倍數。 例如：從1~100的自然數中，任意取出51個數，證明其中一定有兩個數，它們中的一個是另一個的整數倍。 證明：因為任何一個正整數都能表示成一個奇數乘2的方冪，并且這種表示方法是唯一的，所以我們可把1~100的正整數分成如下50個抽屜(因為1~100中共有50個奇數)： （1）{1，1×2，1×22，1×23，1×2?，1×2?，1×26}； （2）{3，3×2，3×22，3×23，3×2?，3×2??}； （3）{5，5×2，5×22，5×23，5×24}; （4）{7，7×2，7×22，7×23}； （5）{9，9×2，9×22，9×23)； （6）{11，11×2，11×22，11×23}； …… （25）{49，49×2}； .…… （50）{99} 這樣，1~100的正整數就無重復、無遺漏地放進這50個抽屜內了。從這100個數中任取51個數，即從這50個抽屜內任取51個數，根據抽屜原則，?其中必定至少有兩個數屬于同一個抽屜，即屬于（1）~（25）號中的某一個抽屜，顯然，在這25個抽屜中的任何同一個抽屜內的兩個數，?一個是另一個的整數倍。 例如：已知在邊長為1的等邊三角形內(包括邊界)有任意10個點。證明至少有兩個點之間的距離不大于1/3。 證明：（如下圖所示）把等邊三角形的每條邊都三等分，并連接各點，將這個三角形化分成9個邊長為1/3的正三角形。10個點放在9個小三角形中，根據抽屜原理必有兩個點在同一個小正三角形內（包括邊界），這兩點之間的距離不大于1/3。 例如：用紅、黃兩種顏色將一個2×5的矩形中的小方格隨意染色，每個方格染一種顏色。證明：必有兩列，它們的小方格染的顏色完全相同。 證明：2×5的矩形有5列，每列有兩個小方格（如下圖a所示）。用紅、黃兩種顏色給每列的小方格隨意染色，只有下面4種情況（如圖b所示）將這4種染色方式看做4個"抽屜"，5列看做5個"蘋果"。由抽屜原理，必有一個抽屜至少有兩個蘋果，即必有兩列染色方式完全相同。 例1：在1991與1991.1之間任取200個數，證明其中必有兩個數，它們差的絕對值不超過1990的倒數。 證明：如下圖所示，1991對應數軸上A點，1991.1對應B點。把線段AB199等分，每個小線段作為一個抽屜，則有199個抽屜，每個小線段的長度為把要取的200個數對應200個點，作為200個東西放入199個抽屜。根據抽屜原理，至少有一個抽屜中至少放入了兩個點，?這兩點的距離一定不超過，即這兩個數差的絕對值不超過1990的倒數。 例2：已知，并且滿足，求證。 證明：由于，將視作鴿子，而將與作為巢穴，根據“鴿巢“原理，在的兩側或都在處，所以將此結論轉化為不等式。因此，，故，即，原等式不成立，當且僅當時，等號成立。 參考資料 > CARL FRIEDRICH GAUSS – The Prince of Mathematics.story of mathematics.2023-11-04形式二
形式三
形式四
形式五
相關表述
推廣
注意事項與舉例
分清物件與抽屜
遵循最差原則
應用
整除問題中的應用
距離問題中的應用
染色問題中的應用
不等式證明的應用