更一般的敘述
有n+1件或n+1件以上的物品要放到n個抽屜中,那么至少有一個抽屜里有兩個或兩個以上物品。
英文:pigeonhole principle
套用
套用廣泛
抽屜原理雖然簡單,但套用卻很廣泛。它可以解答很多有趣的
問題,其中有些問題還具有相當的難度。
下面我們來研究有關的一些問題。
問題1
某校國中部有30個班,每班平均52人。已知這些學生的90%都是在1978~1980年這三年出生的,問他們中有同年同月同日出生的嗎?
解:全校共有學生52×30=1560人,1978~1980年間出生的有1560×90%=1404人。
而這三年有365×3+1=1096天。
由鴿籠原理知道,至少有兩個同學是同年同月同日出生的。
問題2
一個書架有五層,從下至上依次稱第1,第2,…,第5層.今把15冊圖書分別放在書架的各層上,有些層可以不放,證明:無論怎樣放法,書架每層上的圖書冊數以及相鄰兩層內圖書冊數之和,所有這些數中至少有兩個是相等的.
解:我們先把這個實際問題抽象成數學問題.用xi表示第i層放書的冊數(i=1,2,…,5).
若有某個xi=0,則相鄰的一層放書冊數等於它與第i層放書冊數之和,結論成立.
下面考慮xi≥1(i=1,2,3,4,5)的情況:
⑴若x1,x2,…,x5中已有兩數相等,結論成立.
⑵若x1,x2,…,x5兩兩不等,再由它們和為15,所以它們分別取1,2,3,4,5.我們容易驗證,在x1+x2,x2+x3,x3+x4,x4+x5這四個數中不可能同時包含6,7,8,9這四個數(請讀者驗證).這四個數與x1,x2,…,x5總共九個數,但只能有8種取值,因此其中必有兩數相等。
問題3
某個信封上兩個郵政編碼M和N均由0,1,2,3,5,6這六個不同數字組成,現有4個郵政編碼如下:
A:320651,B:105263,C:612305,D:316250.已知編碼A,B,C各恰有兩個數字的位置與M和N相同,D恰有三個數字的位置與M和N相同,試求M和N.
解:
-------------------------------------------------------------
A:320651 恰有兩個數字的位置與M和N相同
B:105263 恰有兩個數字的位置與M和N相同
C:612305 恰有兩個數字的位置與M和N相同
D:316250 恰有三個數字的位置與M和N相同
-------------------------------------------------------------
首先仔細觀察A、B、C。它們雖然均由0、1、2、3、5、6這六個數碼組成,但同一數位上的數字都互不相同。
由鴿籠原理知A、B、C 三數中各數位上都有一個數字是正確的(即與M和N的相應數字相同)。
再把D的各數位上的數與A、B、C 比較,發現D中第3位的6和第6位的0在A、B、C 的第3和第6位上沒有出現,
因此這兩個數碼肯定不正確。由已知D有三個數字正確。因此D中的3、1、2、5四個數字中只有一個不對。
得到結果為:31X25XX=未知數
-------------------------------------------------------------
以下數字必須符合31X25X的數字對應位置。必須滿足D:316250恰有三個數字的位置與M和N相同。
下面逐個討論驗證:
若3不對,取得以下結果:
X1X25X613250 610253
X1X25X013256 016253
若1不對,取得以下結果:
3XX25X301256 306251
3XX25X361250 360251
若2不對,取得以下結果:
31XX5X312056 316052
31XX5X310652 312650
若5不對,取得以下結果:
31X2XX310265 315260
31X2XX316205 315206
-------------------------------------------------------------
回頭校正所有結果,必須滿足A、B、C 當中有且僅有兩個數字的位置與M和N相同
613250X 不符合A,排除
610253
013256X 不符合A,排除
016253X 第3位為6,排除
301256x 不符合C,排除
306251X 第3位為6,排除
361250X 第6位為0,排除
360251X
312056X 不符合B,排除
316052X 第3位為6,排除
310652X 不符合A,排除
312650X 第6位為0,排除
310265
315260X 第6位為0,排除
316205X 第3位為6,排除
315206X 不符合A,排除
-------------------------------------------------------------
最後檢驗所有條件,可知 610253 與 310265 是滿足這些條件的兩個數。
問題4
在前100個自然數中任取51個數,求證:一定存在兩個數,其中一個是另一個的整數倍.
解:我們用鴿籠原理來考慮.把這100個自然數分成50組,使得每組中的數(如果至少含兩個數)是倍數關係,怎樣分組呢 我們記
A1={1,1×21,1×22,1×23,…,1×26},
A2={3,3×21,3×22,…,3×25},
A3={5,5×21,5×22,5×23,5×24},
………………………
A25={49,49×2},A26=,A27=,
………………
A50=.
這50組數中包含了從1到100這100個自然數.根據鴿籠原理從中任取51個數,至少必有兩個數在同一組中,這兩個數中的一個必為另一個的整數倍。
另解:(個人覺得)這個問題有更容易理解的解法
將這51個數,全部轉換為 2^r * b (2的r次方乘以b)
比如這51個數為3、5、7、8、22......
2--> 2^1* 1
5-->2^0* 5
7-->2^0* 7
8-->2^3* 1
22-->2^1*11
......
提取出的51個b都滿足
⑴ 必然是奇數
⑵ 必然小於100
而小於100的奇數只有50個,由鴿籠原理
==> 必然存在2個b相等,則這2個b對應的數必然滿足,其中一個是另一個的倍數
問題5
17個科學家中每個人與其餘16個人通信,他們通信所討論的僅有三個問題,而任兩個科學家之間通信討論的是同一個問題.證明:至少有三個科學家通信時討論的是同一個問題.
解:不妨設A是某科學家,他與其餘16位討論僅三個問題,由鴿籠原理知,他至少與其中的6位討論同一問題.設這6位科學家為B,C,D
若這6位中有兩位之間也討論甲問題,則結論成立.否則他們6位只討論乙,丙兩問題.這樣又由鴿籠原理知B至少與另三位討論同一問題,不妨設這三位是C,D,E,且討論的是乙問題。
若C,D,E中有兩人也討論乙問題,則結論也就成立了。否則,他們間只討論丙問題,這樣結論也成立。
問題6(2002年數學建模d題)
你所在的年級有5個班,每班一支球隊在同一塊場地上進行單循環賽,共要進行10場比賽. 如何安排賽程使對各隊來說都儘量公平呢. 下面是隨便安排的一個賽程: 記5支球隊為A,B,C,D,E,在下表左半部分的右上三角的10個空格中,隨手填上1,2,¼10,就得到一個賽程,即第1場A對B,第2場B對C,¼;,第10場C對E. 為方便起見將這些數字沿對角線對稱地填入左下三角.
這個賽程的公平性如何呢,不妨只看看各隊每兩場比賽中間得到的休整時間是否均等. 表的右半部分是各隊每兩場比賽間相隔的場次數,顯然這個賽程對A,E有利,對D則不公平.
| A | B | C | D | E | 每兩場比賽間相隔場次數 |
A | X | 1 | 9 | 3 | 6 | 1,2,2 |
B | 1 | X | 2 | 5 | 8 | 0,2,2 |
C | 9 | 2 | X | 7 | 10 | 4,1,0 |
D | 3 | 5 | 7 | X | 4 | 0,0,1 |
E | 6 | 8 | 10 | 4 | X | 1,1,1 |