基本介紹
- 中文名：鴿籠原理
- 外文名：pigeonhole principle
- 別稱：鴿巢原理、抽屜原理
- 提出者：路易·波薩
- 提出時間：1834年
- 套用學科：數學
- 適用領域範圍：廣泛套用於各個學科
- 適用領域範圍：組合數學
故事背景,厄杜斯提問題,鴿籠原理,日常運用,一般的敘述,相關問題,
故事背景
路易·波薩（Louis Pósa）是匈牙利的年青數學家，1988年時約40歲。他在14歲時就已能夠發表有相當深度的數學論文。大學還沒有讀完，就已獲得科學博士的頭銜。
他的媽媽是一個數學家。小時他受母親的影響，很愛思考問題。母親看他對數學有興趣，也鼓勵他在這方面發展。她給他一些數學遊戲，或數學玩具啟發他獨立思考問題。在母親的循循善誘之下，他在讀國小時已經自己拿高中的數學書來看了。真正訓練他成為一個數學家的是匈牙利鼎鼎有名的大數學家。
厄杜斯在數論、圖論等數學分支有很深入的研究，他把一生獻給數學，從來沒有想到結婚，只和自己的母親為伴，他經常離開自己的祖國到外國去作研究和演講。在東歐國家裡像厄杜斯能這樣隨意離開自己的國家進出西方世界的數學家並不太多。他到處以數學會友，他在數學方面的多產，以及在解決問題上有巧妙的方法，使他在世界數學界上享有甚高的聲譽。對於他的祖國來講，他重要的貢獻不單是在數學的研究，而是他一回到自己的國家就專心致志地培養年青一代的數學家，告訴他們外國目前數學家注意的問題，擴大他們的視野。
我這裡要講他怎么樣發現路易·波薩的才能的故事。
有一次他從國外回來後，聽到朋友講起有一個很聰明的小東西，在國小能解決許多困難的數學問題，於是就登門拜訪這小鬼的家庭。
波薩的家人很高興請厄杜斯教授共進晚餐。在喝湯的時候，厄杜斯想考一考坐在他旁邊的12歲小孩的能力，於是就問他這樣的一個問題：
“如果你手頭上有n+1個整數，而這些整數是小於或等於2n，那么你一定會有一對數是互素的。你知道這是什麼原因嗎？”
這小鬼不到半分鐘的思考，就很快給出這個問題的解答。他的解答又是那么巧妙，使得厄杜斯教授嘆服。認為這是一個難得的“英才”，應該好好地培養。
厄杜斯提問題
對於許多離開學校很久的讀者，我想做一點解釋厄杜斯提出的問題。
首先我們解釋：一對數是互素是什麼意思？
我們知道如果把自然數1，2，3，4，5，…照大小排起來，從2開始像2，3，5，7，11，13，17，19，23，…，等數都有這樣特別的性質：除1和本身以外，再找不到比它小的數能整除它。
具有這樣特殊性質的數我們稱它為素數（Prime number）。
我們國小時不是學習過把整數因子分解嗎？那就是把整數用素數的乘積來表示。例如50=2×5×5，108=2×2×3×3×3=22×33。
兩個自然數稱為互素（Coprime），如果把它們表示成素數乘積時，找不到它們有公共的素因數。例如{8，11}一對數是互素。10和108不是互素，因為它們有公共的素因數2。
現在讓我們來理解厄杜斯的問題。先對一些特殊的情況來考慮：
當n=2時，我們手頭上有3個整數，這些整數是小於或等於4，可以選出的只是{2，3，4}，不包含1，很明顯的看出{2，3}或{3，4}是互素的。
n=3時，在小於或等於6的整數找4個整數組（不要包含1），可能找出的有{2，3，4，5}，{2，3，4，6}，{3，4，5，6}，{2，4，5，6}等等。你一個個檢查一定會在每組中找出最少一對互素的數。
可以看出隨著n增大時，構造n+1個不同數的數組的個數就會增加很大。如果我們是這樣一個一個地對這些數組來檢查證明，這真會成為：“吾生也有涯，而數無涯”，那時候皓首不但窮盡不了，最後真是要“嗚呼哀哉”了！
如果讀者中有人說：“我有苦幹和拚命乾的精神！”我還是要勸他不要用這樣的苦幹法，應該學會“巧幹”，這才是最重要的。不然的話，人家小孩子用不到半分鐘就解決了的問題，而我們苦幹再加上拚命乾卻花一生還沒法子解決，這不是太浪費生命嗎？
我現在準備介紹波薩對這問題的解法。可是我希望讀者先自己想想看怎么樣解決這問題。如果你能找到和下面不同的解決方法，請來信告訴我。如果你花過一些時間還想不出，那么就請讀下去，你這時就會欣賞波薩解決方法的巧妙，而最重要的你會學懂“鴿籠原理”，說不定以後你成為業餘數學家或者專業數學家還會用到這個原理呢！
波薩是這樣考慮問題：取n個盒子，在第一個盒子我們放1和2，在第二個盒子我們放3和4，第三個盒子是放5和6，依此類推直到第n個盒子放2n-1和2n這兩個數。
現在我們在n個盒子裡隨意抽出n+1個數。我們馬上看到一定有一個盒子是被抽空的。因此在這n+1個數中曾有兩個數是連續數，很明顯的連續數是互素的。因此這問題就解決了！
你說這個解法是不是很容易明白又非常巧妙呢？！
鴿籠原理
波薩在證明過程中用到在數學上稱為鴿籠原理（PigeonholePrinciple）的東西。這原理是這樣說的：如果把n+1個東西放進n個盒子裡，有一些盒子必須包含最少2個東西。 有高六層的鴿籠，每一層有四個間隔，所以總共有6×4=24個鴿籠。現在我放進25隻鴿進去，你一定看到有一個鴿籠會有2隻鴿要擠在一起。
鴿籠原理就是這么簡單，3歲以上的小孩子都會明白。
可是這原理在數學上卻是有很重要的套用。
在19世紀時一個名叫狄利克雷（Dirichlet 1805—1859）的數學家，在研究數論的問題時最早很巧妙運用鴿籠原理去解決問題。後來德國數學家敏古斯基（Minkowski 1864—1909）也運用這原理得到一些結果。
到了20世紀初期杜爾（A．Thue 1863—1922）在不知道狄利克雷和敏古斯基的工作情況下，很機巧地利用鴿籠原理來解決不定方程的有理數解的問題，有12篇論文是用到這個原理。
後來西根（C．L．Siegel，1896—？）利用杜爾的結果發現了現在稱為西根引理的東西，這引理（Lemma）是在研究超越數時是最基本必用的工具。
因此讀者不要小看這個看來簡單的原理，你如果善於運用是能幫助你解決一些數學難題的。
日常運用
我這裡舉一些和日常生活有關的一些問題，你可以看到數學在這裡的運用。 （1）月黑風高穿襪子
有一個晚上你的房間的電燈忽然間壞了，伸手不見五指，而你又要出去，於是你就摸床底下的襪子。你有三雙分別為紅、白、藍顏色的襪子，可是你平時做事隨便，一脫襪就亂丟，在黑暗中不能知道哪一雙是顏色相同的。
你想拿最少數目的襪子出去，在外面借街燈配成同顏色的一雙。這最少數目應該是多少？
如果你懂得鴿籠原理，你就會知道只需拿出去四隻襪子就行了。
為什麼呢？因為如果我們有三個塗上紅、白、藍的盒子，裡面各放進相對顏色的襪子，只要我們抽出4隻襪子一定有一個盒子是空的，那么這空的盒子取出的襪子是可以拿來穿。
（2）手指紋和頭髮
據說世界上沒有兩個人的手指紋是一樣的，因此警方在處理犯罪問題時很重視手指紋，希望通過手指紋來破案或檢定犯人。
可是你知道不知道：在12億中國人當中，最少有兩個人的頭髮是一樣的多？
道理是很簡單，人的頭髮數目是不會超過12億這么大的數目字！假定人最多有N根頭髮。現在我們想像有編上號碼1，2，3，4，…一直到N的房子。
誰有多少頭髮，誰就進入那編號和他的頭髮數相同的房子去。因此張樂平先生的“三毛”應該進入“3號房子”。
現在假定每間房巳進入一個人，那么還剩下“九億減N”個人，這數目不會等於零，我們現在隨便挑一個放進一間和他頭髮數相同的房子，他就會在裡面遇到和他有相同頭髮數目的同志了。
（3）戲院觀眾的生日
在一間能容納1500個座位的戲院里，證明如果戲院坐滿人時，一定最少有五個觀眾是同月同日生。
現在假定一年有三百六十五天。想像有一個很大的鴿子籠，這籠有編上“一月一日”，“一月二日”，至到“十二月三十一日”為止的標誌的間隔。
假定現在每個間隔都塞進四個人，那么 4×365=1460個是進去鴿子籠子裡去，還剩下1500-1460=40人。只要任何一人進入鴿子籠，就有五個人是有相同的生日了。
一般的敘述
抽屜原理的更一般的敘述是:
有n+1件或n+1件以上的物品要放到n個抽屜中,那么至少有一個抽屜里有兩個或兩個以上物品.
此原理用反證法容易證明其正確性.
抽屜原理雖然簡單,但套用卻很廣泛,它可以解答很多有趣的問題,其中有些問題還具有相當的難度.下面我們來研究有關的一些問題.
問題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)的情況:
(1)若x1,x2,…,x5中已有兩數相等,結論成立.
(2)若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四個數字中只有一個不對。
得到結果為：31X25X X=未知數
-------------------------------------------------------------
以下數字必須符合31X25X的數字對應位置。必須滿足D:316250 恰有三個數字的位置與M和N相同。
下面逐個討論驗證:
若3不對，取得以下結果：
X1X25X 613250 610253
X1X25X 013256 016253
若1不對，取得以下結果：
3XX25X 301256 306251
3XX25X 361250 360251
若2不對，取得以下結果：
31XX5X 312056 316052
31XX5X 310652 312650
若5不對，取得以下結果：
31X2XX 310265 315260
31X2XX 316205 315206
-------------------------------------------------------------
回頭校正所有結果，必須滿足A、B、C 當中有且僅有兩個數字的位置與M和N相同
613250 X 不符合A，排除
610253
013256 X 不符合A，排除
016253 X 第3位為6，排除
301256 x 不符合C，排除
306251 X 第3位為6，排除
361250 X 第6位為0，排除
360251 X
312056 X 不符合B，排除
316052 X 第3位為6，排除
310652 X 不符合A，排除
312650 X 第6位為0，排除
310265
315260 X 第6位為0，排除
316205 X 第3位為6，排除
315206 X 不符合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=.
問題5 17個科學家中每個人與其餘16個人通信,他們通信所討論的僅有三個問題,而任兩個科學家之間通信討論的是同一個問題.證明:至少有三個科學家通信時討論的是同一個問題.
解:不妨設A是某科學家,他與其餘16位討論僅三個問題,由鴿籠原理知,他至少與其中的6位討論同一問題.設這6位科學家為B,C,D
若這6位中有兩位之間也討論甲問題,則結論成立.否則他們6位只討論乙,丙兩問題.這樣又由鴿籠原理知B至少與另三位討論同一問題,不妨設這三位是C,D,E,
相關問題
（1）給出任意12個數字，證明當用11來除時，一定有一對數的餘數是相同。 （2）如果在一個每邊都是2單位的正三角形板上隨便釘上17個大
（3）如果在一個每邊都是2單位的正方形板上隨便釘上5根釘，
（4）我們一定能夠在一個每邊都是2單位長的正方形板上適當的釘上9根釘，使它們之中不存在有兩根釘的距離是小於1單位。
（5）（英國數學奧林匹克1975年的問題）在一個半徑為1單位的圓板上釘7個釘，使得沒有兩個釘的距離是大過或等於1，那么這7個釘一定會有一個位置恰好是在圓心上。
（6）任意6個人在一起，一定會有其中兩種情形之一發生：第一種情形──有3個人互相認識。第二種情形──有3個人，他們之間完全不認識。
（7）（a）你能不能在從1到200的整數里挑選出100個自然數，使到任何其中之一不能整除剩下的99個數。
（b）證明如果在從1到200間隨便取101個自然數，那么一定最少有兩個自然數，其中之一能整除另外的數。
（8）隨便給出10個10位數的數字，我們一定能把它分成兩部分，使到每一部分的整數的和是等於其他一部分的整數的和。
