一、一個(gè)匈牙利數(shù)學(xué)家小時(shí)的故事
路易·波薩（Louis Pósa）是匈牙利的年青數(shù)學(xué)家，1988年時(shí)約40歲。他在14歲時(shí)就已能夠發(fā)表有相當(dāng)深度的數(shù)學(xué)論文。大學(xué)還沒有讀完，就已獲得科學(xué)博士的頭銜。
他的媽媽是一個(gè)數(shù)學(xué)家。小時(shí)他受母親的影響，很愛思考問題。母親看他對(duì)數(shù)學(xué)有興趣，也鼓勵(lì)他在這方面發(fā)展。她給他一些數(shù)學(xué)游戲，或數(shù)學(xué)玩具啟發(fā)他獨(dú)立思考問題。在母親的循循善誘之下，他在讀小學(xué)時(shí)已經(jīng)自己拿高中的數(shù)學(xué)書來看了。真正訓(xùn)練他成為一個(gè)數(shù)學(xué)家的是匈牙利鼎鼎有名的大數(shù)學(xué)家。
厄杜斯在數(shù)論、圖論等數(shù)學(xué)分支有很深入的研究，他把一生獻(xiàn)給數(shù)學(xué)，從來沒有想到結(jié)婚，只和自己的母親為伴，他經(jīng)常離開自己的祖國到外國去作研究和演講。在東歐國家里像厄杜斯能這樣隨意離開自己的國家進(jìn)出西方世界的數(shù)學(xué)家并不太多。他到處以數(shù)學(xué)會(huì)友，他在數(shù)學(xué)方面的多產(chǎn)，以及在解決問題上有巧妙的方法，使他在世界數(shù)學(xué)界上享有甚高的聲譽(yù)。對(duì)于他的祖國來講，他重要的貢獻(xiàn)不單是在數(shù)學(xué)的研究，而是他一回到自己的國家就專心致志地培養(yǎng)年青一代的數(shù)學(xué)家，告訴他們外國目前數(shù)學(xué)家注意的問題，擴(kuò)大他們的視野。
我這里要講他怎么樣發(fā)現(xiàn)路易·波薩的才能的故事。
有一次他從國外回來后，聽到朋友講起有一個(gè)很聰明的小東西，在小學(xué)能解決許多困難的數(shù)學(xué)問題，于是就登門拜訪這小鬼的家庭。
波薩的家人很高興請(qǐng)厄杜斯教授共進(jìn)晚餐。在喝湯的時(shí)候，厄杜斯想考一考坐在他旁邊的12歲小孩的能力，于是就問他這樣的一個(gè)問題：
“如果你手頭上有n+1個(gè)整數(shù)，而這些整數(shù)是小于或等于2n，那么你一定會(huì)有一對(duì)數(shù)是互素的。你知道這是什么原因嗎？”
這小鬼不到半分鐘的思考，就很快給出這個(gè)問題的解答。他的解答又是那么巧妙，使得厄杜斯教授嘆服。認(rèn)為這是一個(gè)難得的“英才”，應(yīng)該好好地培養(yǎng)。
厄杜斯以后系統(tǒng)地教這小鬼數(shù)學(xué)，不到兩年的時(shí)間波薩就成為一個(gè)“小數(shù)學(xué)家”了，而且發(fā)現(xiàn)在圖論一些深湛的定理。
二、波薩怎樣解決厄杜斯提的問題
對(duì)于許多離開學(xué)校很久的讀者，我想做一點(diǎn)解釋厄杜斯提出的問題。
首先我們解釋：一對(duì)數(shù)是互素是什么意思？
我們知道如果把自然數(shù)1，2，3，4，5，…照大小排起來，從2開始像2，3，5，7，11，13，17，19，23，…，等數(shù)都有這樣特別的性質(zhì)：除1和本身以外，再找不到比它小的數(shù)能整除它。
具有這樣特殊性質(zhì)的數(shù)我們稱它為素?cái)?shù)（Prime number）。
我們小學(xué)時(shí)不是學(xué)習(xí)過把整數(shù)因子分解嗎？那就是把整數(shù)用素?cái)?shù)的乘積來表示。例如50＝2×5×5，108=2×2×3×3×3＝22×33。
兩個(gè)自然數(shù)稱為互素（Coprime），如果把它們表示成素?cái)?shù)乘積時(shí)，找不到它們有公共的素因數(shù)。例如{8，11}一對(duì)數(shù)是互素。10和108不是互素，因?yàn)樗鼈冇泄驳乃匾驍?shù)2。
現(xiàn)在讓我們來理解厄杜斯的問題。先對(duì)一些特殊的情況來考慮：
當(dāng)n=2時(shí)，我們手頭上有3個(gè)整數(shù)，這些整數(shù)是小于或等于4，可以選出的只是{2，3，4}，不包含1，很明顯的看出{2，3}或{3，4}是互素的。
n=3時(shí)，在小于或等于6的整數(shù)找4個(gè)整數(shù)組（不要包含1），可能找出的有{2，3，4，5}，{2，3，4，6}，{3，4，5，6}，{2，4，5，6}等等。你一個(gè)個(gè)檢查一定會(huì)在每組中找出最少一對(duì)互素的數(shù)。
可以看出隨著n增大時(shí)，構(gòu)造n＋1個(gè)不同數(shù)的數(shù)組的個(gè)數(shù)就會(huì)增加很大。如果我們是這樣一個(gè)一個(gè)地對(duì)這些數(shù)組來檢查證明，這真會(huì)成為：“吾生也有涯，而數(shù)無涯”，那時(shí)候皓首不但窮盡不了，最后真是要“嗚呼哀哉”了！
如果讀者中有人說：“我有苦干和拚命干的精神！”我還是要?jiǎng)袼灰眠@樣的苦干法，應(yīng)該學(xué)會(huì)“巧干”，這才是最重要的。不然的話，人家小孩子用不到半分鐘就解決了的問題，而我們苦干再加上拚命干卻花一生還沒法子解決，這不是太浪費(fèi)生命嗎？
我現(xiàn)在準(zhǔn)備介紹波薩對(duì)這問題的解法�？墒俏蚁Ｍx者先自己想想看怎么樣解決這問題。如果你能找到和下面不同的解決方法，請(qǐng)來信告訴我。如果你花過一些時(shí)間還想不出，那么就請(qǐng)讀下去，你這時(shí)就會(huì)欣賞波薩解決方法的巧妙，而最重要的你會(huì)學(xué)懂“鴿籠原理”，說不定以后你成為業(yè)余數(shù)學(xué)家或者專業(yè)數(shù)學(xué)家還會(huì)用到這個(gè)原理呢！
波薩是這樣考慮問題：取n個(gè)盒子，在第一個(gè)盒子我們放1和2，在第二個(gè)盒子我們放3和4，第三個(gè)盒子是放5和6，依此類推直到第n個(gè)盒子放2n-1和2n這兩個(gè)數(shù)。
現(xiàn)在我們?cè)趎個(gè)盒子里隨意抽出n＋1個(gè)數(shù)。我們馬上看到一定有一個(gè)盒子是被抽空的。因此在這n+1個(gè)數(shù)中曾有兩個(gè)數(shù)是連續(xù)數(shù)，很明顯的連續(xù)數(shù)是互素的。因此這問題就解決了！
你說這個(gè)解法是不是很容易明白又非常巧妙呢？！
三、鴿籠原理
波薩在證明過程中用到在數(shù)學(xué)上稱為鴿籠原理（PigeonholePrinciple）的東西。這原理是這樣說的：如果把n+1個(gè)東西放進(jìn)n個(gè)盒子里，有一些盒子必須包含最少2個(gè)東西。
有高六層的鴿籠，每一層有四個(gè)間隔，所以總共有6×4＝24個(gè)鴿籠�，F(xiàn)在我放進(jìn)25只鴿進(jìn)去，你一定看到有一個(gè)鴿籠會(huì)有2只鴿要擠在一起。
鴿籠原理就是這么簡單，3歲以上的小孩子都會(huì)明白。
可是這原理在數(shù)學(xué)上卻是有很重要的應(yīng)用。
在19世紀(jì)時(shí)一個(gè)名叫狄利克雷（Dirichlet 1805—1859）的數(shù)學(xué)家，在研究數(shù)論的問題時(shí)最早很巧妙運(yùn)用鴿籠原理去解決問題。后來德國數(shù)學(xué)家敏古斯基（Minkowski 1864—1909）也運(yùn)用這原理得到一些結(jié)果。
到了20世紀(jì)初期杜爾（A．Thue 1863—1922）在不知道狄利克雷和敏古斯基的工作情況下，很機(jī)巧地利用鴿籠原理來解決不定方程的有理數(shù)解的問題，有12篇論文是用到這個(gè)原理。
后來西根（C．L．Siegel，1896—？）利用杜爾的結(jié)果發(fā)現(xiàn)了現(xiàn)在稱為西根引理的東西，這引理（Lemma）是在研究超越數(shù)時(shí)是最基本必用的工具。
因此讀者不要小看這個(gè)看來簡單的原理，你如果善于運(yùn)用是能幫助你解決一些數(shù)學(xué)難題的。
四、鴿籠原理的日常運(yùn)用
我這里舉一些和日常生活有關(guān)的一些問題，你可以看到數(shù)學(xué)在這里的運(yùn)用。
（1）月黑風(fēng)高穿襪子
有一個(gè)晚上你的房間的電燈忽然間壞了，伸手不見五指，而你又要出去，于是你就摸床底下的襪子。你有三雙分別為紅、白、藍(lán)顏色的襪子，可是你平時(shí)做事隨便，一脫襪就亂丟，在黑暗中不能知道哪一雙是顏色相同的。
你想拿最少數(shù)目的襪子出去，在外面借街燈配成同顏色的一雙。這最少數(shù)目應(yīng)該是多少？
如果你懂得鴿籠原理，你就會(huì)知道只需拿出去四只襪子就行了。
為什么呢？因?yàn)槿绻覀冇腥齻�(gè)涂上紅、白、藍(lán)的盒子，里面各放進(jìn)相對(duì)顏色的襪子，只要我們抽出4只襪子一定有一個(gè)盒子是空的，那么這空的盒子取出的襪子是可以拿來穿。
（2）手指紋和頭發(fā)
據(jù)說世界上沒有兩個(gè)人的手指紋是一樣的，因此警方在處理犯罪問題時(shí)很重視手指紋，希望通過手指紋來破案或檢定犯人。
可是你知道不知道：在12億中國人當(dāng)中，最少有兩個(gè)人的頭發(fā)是一樣的多？
道理是很簡單，人的頭發(fā)數(shù)目是不會(huì)超過12億這么大的數(shù)目字！假定人最多有N根頭發(fā)�，F(xiàn)在我們想像有編上號(hào)碼1，2，3，4，…一直到N的房子。
誰有多少頭發(fā)，誰就進(jìn)入那編號(hào)和他的頭發(fā)數(shù)相同的房子去。因此張樂平先生的“三毛”應(yīng)該進(jìn)入“3號(hào)房子”。
現(xiàn)在假定每間房巳進(jìn)入一個(gè)人，那么還剩下“九億減N”個(gè)人，這數(shù)目不會(huì)等于零，我們現(xiàn)在隨便挑一個(gè)放進(jìn)一間和他頭發(fā)數(shù)相同的房子，他就會(huì)在里面遇到和他有相同頭發(fā)數(shù)目的同志了。
（3）戲院觀眾的生日
在一間能容納1500個(gè)座位的戲院里，證明如果戲院坐滿人時(shí)，一定最少有五個(gè)觀眾是同月同日生。
現(xiàn)在假定一年有三百六十五天。想像有一個(gè)很大的鴿子籠，這籠有編上“一月一日”，“一月二日”，至到“十二月三十一日”為止的標(biāo)志的間隔。
假定現(xiàn)在每個(gè)間隔都塞進(jìn)四個(gè)人，那么 4×365=1460個(gè)是進(jìn)去鴿子籠子里去，還剩下1500-1460=40人。只要任何一人進(jìn)入鴿子籠，就有五個(gè)人是有相同的生日了。
五、鴿籠原理在數(shù)學(xué)上的運(yùn)用
現(xiàn)在我想舉一些數(shù)學(xué)上的問題說明鴿籠原理的運(yùn)用。
（1）斐波那契數(shù)的一個(gè)性質(zhì)
斐波那契數(shù)列是這樣的數(shù)列：1，1，2，3，5，8，13，21，34，…。從1，1以后的各項(xiàng)是前面兩項(xiàng)的數(shù)的和組成。
在18世紀(jì)時(shí)法國大數(shù)學(xué)家和物理學(xué)家拉格朗日（J．L．La-grange）發(fā)現(xiàn)這斐波那契數(shù)有這樣有趣的性質(zhì)：
如果你用2來除各項(xiàng)，并寫下它的余數(shù)，你會(huì)看到這樣的情形1，1，0，1，1，0，1，1，0，…
如果用3來除各項(xiàng)，寫下它的余數(shù)，你就得到
1，1，2，0，2，2，1，0，1，1，2，0，2，2，1，0，…
如果用4來除各項(xiàng)，寫下它的余數(shù)，你就會(huì)得到
1，1，2，3，1，0，1，1，2，3，1，0，…
現(xiàn)在觀察用2除所得的數(shù)列，從開頭算起每隔三段，后面的數(shù)列就重復(fù)前面的數(shù)列。用3除所得的數(shù)列，從開頭算起每隔八段，后面的數(shù)列就重復(fù)前面的數(shù)列樣子。對(duì)于以4除所得的余數(shù)數(shù)列也有同樣的情況：每隔六段，后面的數(shù)列就重復(fù)前面的數(shù)列樣子。
拉格朗日發(fā)現(xiàn)不管你用什么數(shù)字去除，余數(shù)數(shù)列會(huì)出現(xiàn)有規(guī)律的重復(fù)現(xiàn)象。
為什么會(huì)有這樣的現(xiàn)象呢？
如果我們用一個(gè)整數(shù)K來除斐波那契數(shù)列的數(shù)，它可能的余數(shù)是0，1，2，…，K－1。
由于在斐波那契數(shù)的每一項(xiàng)是前面兩項(xiàng)的和，它被K除后的余數(shù)是等于前兩項(xiàng)被K除余數(shù)的和。（注意：如果這和是大過K，我們?nèi)∷籏除后的余數(shù)）只要有一對(duì)相鄰的余數(shù)重復(fù)出現(xiàn)，那么以后的數(shù)列從那對(duì)數(shù)開始就會(huì)重復(fù)出現(xiàn)了。不同對(duì)相鄰余數(shù)可能的數(shù)目有K2個(gè)，因此由鴿籠原理，我們知道只要適當(dāng)大的項(xiàng)數(shù)，一定會(huì)有一對(duì)相鄰余數(shù)重復(fù)。因此斐波那契數(shù)列的余數(shù)數(shù)列會(huì)有周期重復(fù)現(xiàn)象。
（2）五個(gè)大頭釘在等邊三角板里的位置
有一個(gè)每邊長2單位的正三角形（即三邊都相等的三角形）的三角板。
你隨便在上面釘上五個(gè)大頭釘，一定會(huì)有一對(duì)大頭釘?shù)木嚯x是小過一單位。
你不相信的話，可以做幾次實(shí)驗(yàn)看看是否一直是如此。我現(xiàn)在要用鴿籠原理來解決這個(gè)問題。
在三角板的每邊取中點(diǎn)，然后用線段連結(jié)這些中點(diǎn)，把這正三角形分成四個(gè)全等的小正三角形圖�，F(xiàn)在在每一個(gè)小三角形里任何兩點(diǎn)的距離是不會(huì)超過1個(gè)單位。
由于我們有五個(gè)大頭釘，不管怎么樣放一定有兩個(gè)要落進(jìn)同一個(gè)小正三角形里，因此這兩個(gè)大頭釘?shù)木嚯x是不會(huì)超過一個(gè)單位。
六、動(dòng)腦筋 想想看
（1）給出任意12個(gè)數(shù)字，證明當(dāng)用11來除時(shí)，一定有一對(duì)數(shù)的余數(shù)是相同。
（2）如果在一個(gè)每邊都是2單位的正三角形板上隨便釘上17個(gè)大
（3）如果在一個(gè)每邊都是2單位的正方形板上隨便釘上5根釘，
（4）我們一定能夠在一個(gè)每邊都是2單位長的正方形板上適當(dāng)?shù)尼斏?根釘，使它們之中不存在有兩根釘?shù)木嚯x是小于1單位。
（5）（英國數(shù)學(xué)奧林匹克1975年的問題）在一個(gè)半徑為1單位的圓板上釘7個(gè)釘，使得沒有兩個(gè)釘?shù)木嚯x是大過或等于1，那么這7個(gè)釘一定會(huì)有一個(gè)位置恰好是在圓心上。
（6）任意6個(gè)人在一起，一定會(huì)有其中兩種情形之一發(fā)生：第一種情形──有3個(gè)人互相認(rèn)識(shí)。第二種情形──有3個(gè)人，他們之間完全不認(rèn)識(shí)。
（7）（a）你能不能在從1到200的整數(shù)里挑選出100個(gè)自然數(shù)，使到任何其中之一不能整除剩下的99個(gè)數(shù)。
（b）證明如果在從1到200間隨便取101個(gè)自然數(shù)，那么一定最少有兩個(gè)自然數(shù)，其中之一能整除另外的數(shù)。
（8）隨便給出10個(gè)10位數(shù)的數(shù)字，我們一定能把它分成兩部分，使到每一部分的整數(shù)的和是等于其他一部分的整數(shù)的和。
本文來自：逍遙右腦記憶 http://douzifanli.com/gaozhong/184260.html
相關(guān)閱讀：高中數(shù)學(xué)指導(dǎo)：遇上不會(huì)做的題怎么辦