鴿籠原理
(http://www.vtsh.tc.edu.tw/~jck/topics/pigeon/pigeon.htm)
--------------------------------------------------------------------------------

P博學多聞, Q是他的學生.他們常在一起討論數學.某天...

P:我可以證明,台中市一定有兩個人頭髮一樣多!
Q:這我也可以.
P:說說看!
Q:至少有兩個光頭嘛!
P:你會把 7/23 化為小數嗎?
Q:嘿!簡單啊!
P:試試看吧!
Q:就除一除嘛, 0.304347826086957...???
P:我有一個學生數學向來不錯,幾年前吧,他參加數學系甄試,據說當時教授問他"為什麼 7/23 一定可以化為循環小數?"
這基本的數學原理課本不提,考試不考,當然老師不教(可能也沒時間教),於是他被打敗了!你能不能解釋為什麼 7/23 一定可以化為循環小數嗎?
Q:我是可以算出來啦,只是我不懂你所說的"解釋"到底是什麼意思?
P:其實廣義的講應該這麼說,任意的分數都可以化為循環小數,只是舉 為例罷了
Q:嗯.....那就有點麻煩…
P:我問你,"7隻鴿子飛回鴿籠,如果鴿籠只有6個,則有一個籠子裡會至少會有兩隻鴿子.",這句話你相信嗎?
Q:那當然,想也知道.可是循環小數這問題和鴿子有關係嗎?
P:嗯,你先聽聽,我們稱剛剛這句話為"鴿籠原理",也有人把它叫"抽屜原理".
比較數學化的說法是這樣的,若把kn+1(k>=1)物件放入n個盒子,那麼一定有一個盒子中至少有k+1個物件.
Q:所以說,如果台中市人口超過100萬人,而每個人的頭髮最多1萬根,就至少有101個人的頭髮會一樣多囉?
P:聰明!
Q:那麼,為什麼 7/23 一定可以化為循環小數呢?
P:因為餘數一定小於除數,所以你把7除以23,多除幾次(小數位多一些),就23次吧,假如餘數都不相同,則餘數是1,2,3,...22中的幾個;但是鴿籠原理說,這是不可能的,其中一定至少有兩個餘數相同,所以餘數相同的地方就產生循環!簡單吧!
Q:喔~我知道了.另外,前一陣子我被"聖經密碼"這本書驚嚇到了呢!.
P:為什麼?
Q:作者Michael Drosnin把某一版本的聖經用電腦每隔幾個字母選取一個後排成一列,叫做等距密碼,結果發現許多諸如"拉賓遇刺"這樣的句子.Drosnin在這本書裡宣稱:上帝在聖經裡預警了幾千年後的災難,有憑有據,言之鑿鑿.真教人害怕…
P:先考考你,陳水扁總統說:統一不是唯一的選項時,中共與美國都很生氣,誰在暗爽?
Q:是李登輝嗎?
P:是O.K,全家福,與萊爾富...
Q:原來是腦筋急轉彎!
P:在平面上隨便畫5個點,任3點不共線,則其中一定會有4個點形成一凸4邊形,你相信嗎?
Q:還是腦筋急轉彎嗎?還是說你是要告訴我,這跟聖經密碼有關?
P:這是一位匈牙利數學家Paul Erdös小時候玩的遊戲.1935年,他和George Szekeres證明了只要點數夠多,我們就可以找到任意的凸n邊形.
Q:這有什麼特殊的涵義嗎?
P:那解釋了,我們可以在夜空找到一些星座.
Q 學生:意思是說,我灑一把芝麻在桌上,我就可以把某些點連起來,讓它看起來就像是一隻小白兔?
P:聰明!只要你灑的芝麻夠多.
Q:數學有點好玩耶,也許我可以考慮念數學系.但這跟聖經密碼有關係嗎?
P:後來,Erdös發現他的定理只不過是Ramsey定理的特例.
拉姆西(Frank Plumpton Ramsey 1903~1930)是一個非常聰明的英國數學家,不幸年青早逝.Ramsey定理的數學形式很抽象,他本人倒是舉了一個有名的例子:世界上任意6個人中,總有3個人相互認識,或3個人互相皆不認識.
Q:也許我的腦筋要轉好幾圈才能理解.
P: 另外,把1,2,3,4,5作任意重排,則其中至少有3個數是遞增或遞減(例如排成1,4,5,3,2則1,4,5是遞增).
Q:這也是小時候玩的遊戲嗎?
P:沒錯!長大後就變成"在前n2+1個自然數中,至少必定有n+1個是有序的"(由小到大,或由大到小).
Q:這大概很難證明吧!我看我還是不要念數學系的好…你還沒有告訴我聖經密碼的事哩.
P:Ramsey定理說,"不可能完全無序",意思就是說,只要點數夠多,我們就可以在裡面"看出"你要的任何圖像,所以你可以在夜空中看到各種星座;同理,叫一隻猩猩在打字機上亂打,只要字母夠長,你可以找到你要的任意有意義的句子,Drosnin用電腦做所謂等距密碼,其實道理是一樣的.
Q:你的意思是說,我用其它書也可以找到"密碼",例如莎士比亞全集也可以囉?
P:對,如果你還想念數學系,我建議你用尤拉全集.無獨有偶地,一位高中生O'Leary把 寫成小數點,對應到26進位數,每一個數對應一個英文字母.在"不可置信的Pi碼"一文中,他把3.14 15 9 26 5對應到C.N O I S E,而NOISE是一個有意義的字;接著,他把 Pi 用二進位表示,做了許多花樣後也找到了"密碼",宣稱可以預測股票市場,並且宣稱其中一個圖像是下一屆總統的側面圖(當然,他找到隱而不宣的理由).
其實,這些都是無稽之談. 這些就是李國偉先生所謂的偽科學,你可以看看李先生的書"一條畫不清的界線".在科學與偽科學之間畫一條清楚的界線不是一件容易的事.
Q:聽你這樣講,我還是不懂Ramsey定理,但總算是鬆了一口氣了.

鴿籠原理又稱為Dirichlet原理(P. G. L. Dirichlet 1805-1859),

Ramsey定理的證明用到了鴿籠原理,Ramsey定理是鴿籠原理的推廣,這是組合學的範疇.
可別小看了組合學,李國偉先生先專攻數理邏輯,後來轉攻組合學,使台灣成為一個堅強的組合學研究團隊而揚名國際.
你只要到"大英百科全書輸入"Ramsey Theorem"就可以找到Ramsey定理的內容

--------------------------------------------------------------------------------
習作

1. 為什麼 7/23 一定可以化為循環小數?
2. 將9個正整數a1,a2,...a9重排成為b1,b2,…b9,則 (a1-b1)(a2-b2)…((a9-b9)必為偶數
3. 任給7個相異整數,求證其中必有2數,其和或差是10的倍數
4. 任給52個整數,必有兩個數,其和或差是100的倍數
5. 座標平面上任5個格子點,至少有兩點,其連線段中點也是格子點
6. 座標平面上有相異的10個點，其中沒有三點在同一條直線上，每一點均為格子點，試證明這10個點兩兩之間的連接線段中，必有一個異於這10個點的格子點。( 點A為格子點的意思，就是點A座標(m , n)中，m , n均為整數) --中學生通訊解題第三期 88301
7. 邊長為1的正三角形邊上有10點,則必定有2點,其距離小於或等於 1/3
8. 在邊長=1的正方形內任取5個點 試證至少有兩個點的距離小於或等於 1/sqrt(2)
9. 在邊長=1的正方形內任意放入9個點,則其中至少有3個點,其所圍成的三角形面積不超過 1/8
10. 已知ABC的面積=1,D是AB上任一點,E是AC上任1點,F是DE上任一點;則 BDF,CEF中至少有1個面積小於或等於 1/8
11. 從1到100的正整數中任取51個數,則其中會有1個數是另外1個數的倍數(然後改成從1到2n的正整數中任取n+1個數)
12. 設a1,a2,...,an是正整數數列,則至少存在正整數 k,l;其中0< k< l< m+1,使得ak+ak+1+...+al是m+1的倍數
13. 會議中有n個人參加,每一個人至少認識其中另一個人,則n個人中至少有2人認識的人數相同,為什麼?
14. 對於任一實數r,存在一分數p/q,使得 |r-p/q| < 1/q^2 -- P.G.L.Dirichlet原理 1805-1859
15. 在一圓上取6個點,在每兩點間作連線段,如果把每個線段任意地塗成咖啡色或藍色,則有一個 三角形,它的三邊同色. 世界上任意6個人中,總有3個人相互認識,或互相皆不認識[解答15] --Frank Plumpton Ramsey 1903~1930
16. 在前n^2+1個自然數中,至少必定有n+1個是有序的(由小到大,或由大到小) ( 1913~1996)
17. 由算術數列1,4,7,...100中任取20個數,其中必有兩個,其和為104
18. 任給5個整數,則其中必有3個數的和是3的倍數
19. 在一個半徑=6的圓內任意放6個半徑=1的小圓,試證總會有一個空位置放入一個半徑=1的小圓
20. 設m是任一偶數,m個整數a1,a2,...am滿足
1 <=a1<= a2 <=... <=am <= m
a_1+a_2+...+a_m=2m
試證:一定可以把這m個數分成兩組,使得每一組的和都是m

--------------------------------------------------------------------------------
解答

[解答1] 因為餘數一定小於除數,所以你把23除以7,多除幾次,就23次吧,假如餘數都不相同,則餘數是 1,2,3,...22;但是抽屜原理說,這是不可能的,其中一定至少有 兩個餘數相同,(就是說,現在你把23個 蛋放入22個碗中)餘數相同的地方就產生循環!
如果我們"認定"有限小數也是一種循環小數,,則我們可以說所有的分數都是循環小數,所有的循環 小數都是分數.
一個可以化為有限小數的分數長什麼樣子?
[解答2] 如果(a1-b1)(a2-b2)…((a9-b9)是奇數,則 對i=1,...,9,ai-bi是奇數,則a1,a2,…a9中奇數與偶數個數一樣多,矛盾!  數學的發現趣談 p.028
[解答3] 考慮 10k, {10k+1,10k-1}, ... ,{10k+5,10k-5} 6個"巢" 則至少有兩個數在同一巢內
[解答5] 假設這5個點的座標為(ai,bi);(a1,b1)與 (a2,b2)的中點為((a1+b1)/2,(a2+b2)/2) ,所以,只要a1與b1,a2與b2皆有相同的奇偶性 即可,但是任意平面上格子點分成4類:(奇,奇),(奇.偶),(偶,奇),(偶,偶);由鴿籠原理,5個點至少有兩個點有相同的奇偶性.
[解答6] 因為10個點座標均為格子點，根據整數的奇偶性來分類，可分為(奇,偶)、(偶,奇)、(奇,奇)、(偶,偶)四個情形，故必有二個頂點的座標其奇偶性一樣，設這兩個點為A,B，則線段AB的中點M必為格子點，因為10點中任3點不共線，所以M必異於這10點。
[解答8] 把原正方形切成4個全等的小正方形
[解答9] 用3條平行上下底的直線把此正方形平分成4個矩形,則至少有3個點會落在同一個矩形內
[解答11] 1到100之間奇數與偶數各有50個,把它們寫成a_i = 2^m b_i ,其中若a_i是奇數,則m=0;又b_i是1,3,5,...99裡面的數,今任取51個數,由鴿籠原理,存在兩個數長成2^m b_k, 2^n b_k的樣子,亦即此兩數有倍數關係
[解答14] 數學探奇 p.87
[解答15] 考慮由點1與其他5點所連之線段,因為有5個線段,由鴿籠原理至少會有3個線段同色(圖中之咖啡色),假設是12,13,15;假設任3點所構成的的邊皆不同色,所以23為藍色,同理,35為藍色,則在考慮25時得到矛盾
[解答16] 抽屜原理及其他,凡異出版社 p.14
[解答20] 抽屜原理及其他,凡異出版社 p.66

--------------------------------------------------------------------------------
參考文獻

1. 抽屜原理及其他 p.97 凡異出版社
2. 數學傳播季刊14卷第4期 p.100
3. 數學傳播季刊21卷3期 p.63 棋盤染色問題與二部Ramsey數
4. 通過問題學解題 p97,九章出版社
5. 數學探奇 p.87 米蓋爾.德.古斯曼 著
6. 不只一點瘋狂 p.109
7. 數學的發現趣談p.028 蔡聰明教授 著
8. 科學教育月刊 232期
9. 不可置信的Pi碼 (http://www.sciencenews.org/articles/20000401/mathtrek.asp)
10. 一條畫不清的界線 第10章 李國偉 著