2009年11月6日

鴿籠原理

作者/游森棚

最近在大三開的「組合數學」課堂上,教到鴿籠原理(pigeonhole's principle):十隻鴿子飛到九個籠子中,必有一個籠子裡有兩隻以上的鴿子

學生嗤之以鼻,這個原理乍看之下簡直沒有數學可言。「這不是廢話嗎!」一個學生當下吐槽。我笑了。接下來就連珠砲地問了他們一堆問題:

「所以,隨便挑三個人,必定有兩個人同性別囉?」「當然。」
「隨便挑八天,一定有兩天同樣是星期幾囉?」「對。」
「隨便挑13 個人,一定有兩個人同生肖囉?」「……嗯。」
「隨便挑367 個人,一定有兩人生日同一天囉?」「……嗯。」
人的頭髮最多只有10萬根。楠梓區人口一共17 萬人,所以其中一定有兩個人頭上的頭髮一樣多根囉?
學生開始露出驚訝的表情,「怎麼可能?」「可是,可是……對耶。」
「你們剛剛不是說鴿籠原理是廢話嗎?」這下換我吐槽回去。

鴿籠原理,又叫作狄利克雷(Dirichlet)原理,是乍看無用,卻應用廣泛有威力的原理之一。用鴿籠原理可證明出許多神奇的結果。有些問題明明看似沒有條件,居然可以由鴿籠原理配合嚴格的數學推論,得出意想不到的結果。課堂上我講的第一個例子是:在紙上隨便寫七個自然數成一列。則不管你怎麼寫,一定有相鄰的幾個(可以只有一個)數加起來是7的倍數。比如寫3, 5, 3, 18, 9, 124, 99 ,則3+ 18 = 21 就是7 的倍數。不相信的讀者可以多寫幾串試試看!

證明過程是這樣的:假設寫下來的數是a1, a2,..., a7 。考慮由第一項開始加的部分和

S1 = a1
S2 = a1 + a2
S3 = a1 + a2 + a3
S4 = a1 + a2 + a3 + a4
S5 = a1 + a2 + a3 + a4 + a5
S6 = a1 + a2 + a3 + a4 + a5 + a6
S7 = a1 + a2 + a3 + a4 + a5 + a6 + a7

如果S1,...S7之中有7的倍數,那就得證。如果都沒有,則S1,...S7中的每一個除以7都餘1, 2,3, 4, 5, 6其中之一。但是現在共有S1,...S7這七個和,餘數只有1, 2, 3, 4, 5, 6 這六種情形。因此由鴿籠原理可知,一定有某兩個和除以7的餘數相同。為說明方便,假設是S2 和S6 除以7 的餘數相同。因此把兩者相減,就會是7的倍數。而S6 - S2 =(a1 + a2 + a3 + a4 + a5+ a6)-(a1 + a2)= a3 + a4 + a5 + a6 ,會剩下連續的幾項,得證。

但下一個看似更加無厘頭的敘述,才是鴿籠原理最經典的例子:世界上任意選六個人出來。則這六個人之中,其中一定能找到三個人彼此互相認識,或是找到三個人互相不認識。這個定理敘述是令人驚愕的——「任意」選六個人,都會有這樣的結果喔!

證明方法是這樣的:用六個點代表六個人。兩人認識就連實線,兩人不認識就連虛線。所以我們要證明,不論這六個人的關係怎樣,一定能找到一個實線三角形(表示有三人兩兩彼此認識),或是一個虛線三角形(表示有三人兩兩不認識)。現在考慮其中一個點,代表老王。老王要連出去五條線,因此由鴿籠原理,必定有三條線同是實線或同是虛線。不妨設老王連到A、B、C三點,都是實線。現在,如果AB、BC、CA之中有任何一條實線,則我們就找到了一個實線三角形。若AB 、BC、CA都連虛線,則我們就找到一個虛線三角形,得證。【更詳細的內容,請參閱第479期科學月刊】

回本期目錄

沒有留言: