有些論斷看似沒有道理，比如“一個班級裡肯定有兩個人生日在同一個月份”、“世界上肯定有兩個人頭髮數一樣多”等等，但是仔細一想還真是對的。

注：人類的頭髮根據種族和髮色的不同，數量略有不同，最多在12萬根左右；目前世界上的總人口超過了74億；

再舉一個例子，現在有十隻鴿子但只有九個籠子，那麼必定有一個籠子裡至少有兩隻鴿子。因為九個鴿子先各佔一個籠子，那麼第十隻就只能和其他鴿子擠擠了。

而上述看似顯然的一個結論就是“鴿籠原理”（The Pigeonhole Principle），也叫“抽屜原理”。

如果有

只或者更多的鴿子，而只有

個籠子，那麼必定有一隻籠子中至少有2只鴿子。

如果把

件東西放入

個箱子中，那麼必定有一個箱子中至少有

件東西，其中

是取上整函式，不小於該值的最小整數。

不要小看這個原理，感覺就是說了一句廢話，但運用到某些競賽題中會有四兩撥千斤的作用。

下面我們透過競賽題來實戰一下，比如第一題2016AMC10A的第20題

題意：從1到2006中隨機取出6個數（包括1和2006）， 問其中存在一對數的差是5的倍數的機率是多少？

首先這是一道機率題，按照古典概型的做法我們要先搞清楚樣本空間，數數樣本總數，這個比較簡單

，但是滿足要求的樣本有多少個呢？這是一個問題，搞清楚了那麼機率也就算出來了。

不過這道題有點不一樣，不是這個套路了。下面我們證明一下隨機選出來的6個數必定有一對數，它們的差值是5的倍數。（有點不按套路出牌）

證：因為一個數被5除，剩下的餘數只有5種

，如果隨機取6個數，必定有兩個數的餘數相同，

。所以，必定存在一對數，它們的差是5的倍數，

。因此，機率為1，這是必然事件。

類似的，還有下題

題意：證明從100個整數中任意挑選15個數，其中必定存在一組數使任意一對數的差都是7的倍數。

感謝yyx和xielhy890指正。

與上題不同，這是是一道證明題，但是做法是類似的。

證：被7除的於是有

7種情況，那麼把100個數放入到這7個“籠子”中，根據鴿籠原理可知，必定有一個“籠子”中至少有

個數，得證。

鴿籠原理對於解決存在性、任意性的問題是一把好手，解題的關鍵是構造籠子，這也是此類問題的難點。在此基礎上更難的題型是，答案需要你自己去猜，然後再證明，往往是問滿足條件的最小值是多少。

如下題

題意：一共有8各箱子，每個箱子裝了6個球。每個球從

種顏色中挑一種著色，要求每個箱子中球的顏色各不相同，兩種不同顏色的球在一起最多一次。問最少需要多少種顏色的球？

根據題意

肯定是滿足的，每個球的顏色都不相同，但這肯定不是最少的，所以我們要先猜去這個最小的

，並且要說明比這個小的都不能滿足要求。

證：首先說明

是可行的，我們可以給出如下的著色方法：

其中每一行代表一個箱子，每一列代表一個球，數字代表一種顏色；

下面證明

是不可能滿足題意的。

（1）如果有一種顏色的球在5個或者更多的箱子中出現，那麼必須要有

種顏色，矛盾；

（2）如果有一種顏色的球在4個或者更多的箱子中出現，那麼前4個箱子中一定含有

種顏色。

那麼在第5個箱子中6個球可以從前4個箱子中挑4中顏色的球，但是剩下的兩個必須要與前面21種顏色不同，所以至少需要23種顏色，矛盾；

（3）那麼根據鴿籠原理一定有一種顏色的球出現在3個不同的箱子中（48個鴿子到22個籠子中）不妨假設顏色1出現在了3個箱子中，那麼這三個箱子的顏色分別為

剩下的五個箱子中的6個球分別都可以從前三個箱子中挑3種顏色進行著色，不妨設為

於是我們還剩下22-16=6種顏色把15個球著色。與前面的分析類似，首先肯定不能有一種顏色的球出現在3個或者更多的箱子中，因為這樣就需要

種顏色，矛盾；於是就只能有1種顏色的球出現在2個箱子中，而剩下的兩隻箱子裡面的球可以按照下圖進行著色

到這裡，可以發現至少需要

種顏色，這與

矛盾。

綜上所述，最少的

為23。

這道題要比前面兩題難了很多，不是一個level的，但是其中都運用了鴿籠原理。這樣的題目還有問題，有一個比較有趣的問題可以思考下：

答案是肯定的，任意六個人中，必定存在三個人相互認識或三個人相互不認識。這其實就是Ramsey number，

，可以利用鴿籠原理證明。

鴿籠原理一般應用在一些證明題中，特別是

存在性的證明

，在競賽選擇題中就出現比較少了，畢竟選擇題只需要一個答案就夠了。至於難點，前面也提到了，如何巧妙地構造籠子就要靠本事了。

一己拙見，歡迎大家一起交流討論~~

想了解更多國際數學競賽及課程，可參閱：

微信訂閱號：數你好看