鴿籠原理 王安蘭老師

又名鴿巢原理(The Pigeonhole Principle)或Dirichlet抽屜原理(The Dirichlet Drawer Principle)或重選原則。

原理1.如果有n+1隻鴿子要飛進n個籠子內休息，那麼必定有一個籠子內停了兩之或兩隻以上的鴿子。

原理2.將nr-n+1個物品放入n個盒子內，則至少有一個盒子有r或r個以上物品。

原理3.將個物品放入n個盒中，則必有一盒內至少含有個物品，或者有一盒內至少含有個物品……，或者有一盒內至少含有個物品()

運用鴿籠原理有兩個主要環節：認識到運用鴿籠原理的必要及製造鴿籠。處理好這兩個環節重要的還在於對問題深刻認識，以及經驗和機敏。

(一) 日常運用

例1. 在一個月黑風高的晚上，你的房間電燈壞了，伸手不見五指，而你想外出，於是自抽屜內摸出襪子穿。假設你有黑、白、藍襪各一雙，在黑暗中你最少要取多少隻襪子才能確定至少有同顏色的一雙？

例2. 在某一宴會裡，席開100桌，有甲、乙兩位多年不見的老朋友談笑言歡當年，後來甲隨意的說：「在這麼多客人中，一定有兩人認識的朋友(在此宴會中)是一樣多，你信不信？」你認為這個結論對嗎？(認識是指互相認識)

(二) 如何確定鴿與籠

有些問題明知道需要運用鴿籠原理去解決，又不知從何下手，這時就需深入分析問題，以洞察問題本質，適當地做些轉化工作，簡潔地選擇‘鴿子’與‘籠子’。

例3. 在{1,2,3,……,10}中任取6數，求證一定存在兩數，其中一個是另一個的整數倍。

練習題：

(1) 在1,2,……,200的自然數中，任取101個數，證明一定存在兩個數，其中一個數是另一個數的整數倍。(hint:分100堆，有規則地分)

(2) 在1~91個自然數中任取10個數，求證其中存在兩個數，他們的比值在

再來，我們看兩種常見的籠子製造法，其中特別注意的是，鴿籠原理可能在一題中多次使用才能解出答案。

1.利用餘數選籠子

例4.(1)給定任何52個正整數，證明必存在2個數，它們的和或差可被100整除。

(2)任意給定10個自然數，證明可用減、乘兩種運算，把它們適當連起來，其結果能被1890整除。

練習題：

(3) 設n是大於1的奇數，證明中至少有一個數能被n整除。

(4) 設M是由1985個不等的正整數組成，其中每個正整數的質因數均不大於26，證明集合M至少可找到四個相異數，它們的乘積是某個整數的四次方。

2.分割圖形製造籠子：

例5.在邊長為1的正方形內有5個點，證明至少有兩個點，它們的距離小於

例6.證明9個小朋友在邊長為8公尺的正三角形的草地上玩，，每個人的位置看成一個點，如果以他們所站的位置為頂點，則9個小朋友中，至少有三個小朋友所站的位置形成三角形面積不超過7平方公尺。

練習題：

(5) 在邊長為1的立方體內有9個點，證明至少存在兩點，它們的距離小於

(6) 在邊長為1的正三角形內有5個點，證明至少有兩點距離小於。

(7) 在邊長為1的正三角形內有k個點，要證明至少有兩點，它們的距離小於

(8) 在一個半徑為1的圓板上釘上七根鐵釘，使得任何兩釘的距離大於或等於1，那麼這7根釘子一定會有一根其位置恰好是在圓心上。

(9) 有111個點放在一個邊長為15的正三角形中，證明用一個直徑為的圓形硬幣，至少可以蓋住上述點中的3個。(覆蓋時，硬幣的部分可以在三角形外。)

3.利用奇偶性分析分類

例7.(1)平面上5個格子點，證明至少有兩點的中點也是格子點。

(2)平面上13個格子點，證明必有某四點的重心也是格子點。

4.利用染色分析分類

例8.十七位科學家每一個人和其他所有人都通信，在他們的來往書信中僅討論3個題目，而每兩個科學家僅討論一個題目，證明：至少有3個科學家他們互相討論著同一個題目。