鴿籠原理    王安蘭老師

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

 

 

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

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

原理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個科學家他們互相討論著同一個題目。