本文略經(jīng)改編原載於數(shù)學(xué)傳播第二卷第四期

1、本文略經(jīng)改編原載於數(shù)學(xué)傳播第二卷第四期鴿籠原理謝聰智§ I. 鴿籠原理 § II. 三個(gè)知友或三個(gè)陌生人 § III. 鴿籠原理的挑戰(zhàn) I. 鴿籠原理鴿籠原理是說(shuō)將 k 個(gè)東西分成 n 類，若 則有一類東西之?dāng)?shù)目大於或等於 。十隻鴿子分放在九個(gè)籠中，必有一籠至少放二隻鴿子。五房客四房間，一定有二房客共一房間。三男追二女，必有二男為情敵。十三人同行，必有二人同月生。五人分十六本書(shū)，必然有人至少獨(dú)得四本書(shū)。這些都是鴿籠原理在生活中常碰到的實(shí)例。這樣平凡的道理人人在諸多待人接物中，不假思索屢用不爽。道理雖然簡(jiǎn)單，巧妙地運(yùn)用卻有意想不到的驚奇結(jié)果。1.1. 連勝 21 次

2、的圍棋高手沈士海是位圍棋新秀，去年參加全國(guó)圍棋名人大賽，從地方初選到最後名人爭(zhēng)奪戰(zhàn)，一連比賽了11星期。沈高手之戰(zhàn)績(jī)輝煌，優(yōu)勝記錄是：每日至少勝一次；每星期最多勝12次。由此記錄可推得在一段連續(xù)的日子裏，沈棋士不多不少連勝了21次。 結(jié)論似乎有點(diǎn)出奇。想一想，再看下面的證明。 設(shè) 等為第 1 天，第 2 天，最後第77天沈高手勝棋的累積數(shù)。由於每天至少勝一次及每星期最多勝12次，得 。 令 。則 。 及 共有154個(gè)數(shù)，但其值落在 1 至153之153個(gè)數(shù)中。由鴿籠原理，其中必有二個(gè)數(shù)其值相同。由(1)及(3)， 之間彼此不相等， 之間亦彼此不相等。因此某一 等於某一 。此即 或 。換言之，從

3、第 天至第 天，沈棋士不多不少勝了21次。1.3. 科學(xué)小飛俠的紙牌遊戲小飛俠一號(hào)鐵雄與三號(hào)珍珍，在掃蕩惡魔黨之餘暇，常愛(ài)玩一種鬥智的紙牌遊戲。遊戲開(kāi)始前，兩人各準(zhǔn)備五張空白的紙牌，各按自己的意思在每張牌上寫一個(gè)號(hào)碼，然後各自將五張寫上號(hào)碼的牌與對(duì)方交換。遊戲開(kāi)始，兩人猜拳決定先後秩序輪流出一張牌。當(dāng)出手之牌與桌面上適當(dāng)挑選的牌加起來(lái)，其點(diǎn)數(shù)和為10之倍數(shù)時(shí)，出牌者得勝，比賽結(jié)束；否則輪到對(duì)方出牌繼續(xù)比賽。若最後各人把百?gòu)埮瞥鐾甓捶謩儇?fù)，比賽即為雙和。這遊戲既簡(jiǎn)單又有趣，鐵雄與珍珍玩得津津有味。但很奇怪，玩了千百次的記錄中，各有勝負(fù)，但從來(lái)沒(méi)有雙和的情況發(fā)生。有一次，他們就把這遊戲是否有雙和

4、的問(wèn)題請(qǐng)教南宮博士。他思索片刻，洞察其中道理後說(shuō)：是的，十個(gè)任意數(shù)目統(tǒng)統(tǒng)加起來(lái)若不是十的倍數(shù)，其中必有一部份加起可被十除盡。接著南宮博士又說(shuō)：事實(shí)上，任意給定 n 個(gè)正整數(shù)的數(shù)列 a1, a2,an，必定有一段連加起來(lái)是 n 的倍數(shù)。用鴿籠原理試證明看。小飛俠鐵雄不僅武功非凡，智力亦高，經(jīng)南宮博士一提醒，花了一天一夜苦思，果然看透了問(wèn)題並想出了證明。各位讀者，想一想，再看以下鐵雄的證明。 ， 為給定之 n 個(gè)正整數(shù)列，設(shè) 。以 n 除 得商 ，餘 寫成 。若某一 rk=0 則 sk 為 n 之倍數(shù)即得結(jié)論，因此假定所有 , j=1,2,n，則 r1,r2,rn 等 n 個(gè)數(shù)，其值皆落在 1,2

5、,n-1 等之 n-1 個(gè)數(shù)中，由鴿籠原理，必有某一 rk 等於某一 ri。故 sl-sk 為 n 之倍數(shù)。此即說(shuō) 可被 n 除盡。1.4. 十人中之高矮次序十個(gè)人任意排成一列必定有四人是按高矮順序排列。事實(shí)上，一般的情形，任意長(zhǎng)度為 n2+1 之實(shí)數(shù)敘列必包含有 n+1 長(zhǎng)度為 n+1 之遞增或遞減子敘列。下面是組合學(xué)大師耶迪西 (Erdös) 的證明。假設(shè)給定之實(shí)數(shù)敘列 a1,a2,an2+1 中沒(méi)有長(zhǎng)度為 n+1 的遞增子敘列，我們將證明必定有長(zhǎng)度為 n+1 之遞減子敘列。對(duì)任意 ai 考慮所有以 ai 為起點(diǎn)之遞增子敘列。令 mi 為此種遞增子敘列中可能達(dá)到之最大長(zhǎng)度。由開(kāi)始

6、的假定得 。m1,m2,mn2+1 為 n2 +1 個(gè)數(shù)，其值落在 1,2,n 之 n 個(gè)數(shù)中，由鴿籠原理，必有 n+1 個(gè) mi 取同一值。令 且 。若 則 接上以 為起點(diǎn)之最長(zhǎng)遞增序列構(gòu)成以 為起點(diǎn)，長(zhǎng)度為 之遞增子序列， 因此 。此與(4)式矛盾，故 ，同理 , ， 等。此即 是長(zhǎng)度為 n+1 之遞減子序列。1.5. 101個(gè)數(shù)中的奇蹟從 1、2、3、200 的二百個(gè)數(shù)中任取 101 個(gè)數(shù)則其中必定有二數(shù) s,t，使得 s 是 t 的因數(shù)或 t 是 s 的因數(shù)。想一想，再看以下的證明。 任意選取之 101 個(gè)數(shù)記為 a1,a2, , a101。將 ai 中所有含 2 之因數(shù)刮出，寫成 ，

7、 其中 pi 為奇數(shù)。 p1, p2,p101 等 101 個(gè)數(shù)，其值落在 1,3,5, ,199 等之 100 個(gè)數(shù)中。由鴿籠原理，知道某兩個(gè) pi 相等。設(shè) pk = pu = p 則 及 ，令 s = ak, 及 t = au，則 s,t 滿足所要的條件。1.6. 圓盤上之七點(diǎn)半徑為 1 的圓盤上有七點(diǎn)，其中任意二點(diǎn)的距離都不小於 1。則七點(diǎn)中有一點(diǎn)為圓心。結(jié)論有點(diǎn)出奇，想一想，再看以下證明。 將圓盤如圖一分成六塊相等之扇形 A1 O A2 ,A2 O A3, , A6 O A1 等。令 圖一 除圓心外，圓盤上之任一點(diǎn)都屬同而僅屬於某一Si 。若七點(diǎn)中無(wú)一為圓心，則其中有二點(diǎn)屬於同一 S

8、i。但 Si 中之任意二點(diǎn)的距離都小於1，故不可能七點(diǎn)中無(wú)一點(diǎn)為圓心。結(jié)論確定。1.7. 正三角形內(nèi)之三個(gè)區(qū)域正三角形 ABC 各邊長(zhǎng)為 1，將 ABC 所圍成的點(diǎn)集合，任意分成 S1,S2,S3 三區(qū)域，則必定有某一 Si 之直徑大於或等於 了。此中所謂點(diǎn)集合 S 的直徑是指 S 中任意兩點(diǎn)距離的最大數(shù)。由於 S1,S2,S3 之形狀毫無(wú)限制，初看，問(wèn)題是似乎很難，想一想，再看以下的證明。 令 O 點(diǎn)為正三角形的中心，O、A、B、C 中任意兩點(diǎn)的距離都大於或等於 。視 O、A、B、C 四點(diǎn)為鴿， S1、S2、S3 為籠，由鴿籠原理，某一 Sk 包含此四點(diǎn)之兩點(diǎn)。因此 Sk 之直徑大於或等於

9、。1.8. 廣義的鴿籠原理給定正整數(shù) q1, q2,qn，將 k 個(gè)東西分為 n 類，若 則一定有某第 i 類東西個(gè)數(shù)大於或等於 qi 個(gè)。這是鴿籠原理一般情況。它的證明很簡(jiǎn)單，假若結(jié)論不確，即是說(shuō)第 1 類東西小於 q1，第 2 類小於 q2，第 n 類小於 qn。則所有東西總和 此與前提矛盾故不可能。當(dāng) 時(shí)即為原來(lái)的鴿籠原理。我們以 來(lái)表示 ， 稍後再討論其推廣。II. 三個(gè)知友或三個(gè)陌生人鴿籠原理有一種更廣義的形式，那就是組合學(xué)上有廣泛應(yīng)用的蘭姆西 (Ramsey) 定理，定理敘述前先看一個(gè)特例。 2.1. 三知友或三鮮人一群人，人數(shù)大於等於 6，必然有三知友兩兩彼此認(rèn)識(shí)或有三新鮮人兩兩

10、彼此都不認(rèn)識(shí)。以下就是證明。 任取一人名之為 A，其他人，人數(shù)至少為 5，可分為二類。與 A 認(rèn)識(shí)者為一類，與 A 不認(rèn)識(shí)者為另一類，由鴿籠原理，必有一類人數(shù)大於等於 3。令此三人之名為 B、C、D。 若 B、C、D 皆與 A 認(rèn)識(shí)且其中有二人彼此相識(shí)，則 A 及此二人為三知友，不然 B、C、D，兩兩不認(rèn)識(shí)則 B、C、D 為三新鮮人；若 B、C、D 皆與 A 不認(rèn)識(shí)且其中有二人彼比不相識(shí)，則 A 與此二人為三新鮮人，不然 B、C、D 中兩兩互相認(rèn)識(shí)則 B、C、D 為三知友。無(wú)論有三知友或三新鮮人，結(jié)論都是對(duì)的。 6 是滿足上述性質(zhì)最小整數(shù)，它有特殊的意義，我們記為 N(3,3;2) = 6，表

11、示一群人 S，人數(shù)未知。但 S 中任 2 人的關(guān)係分為兩類，且知道 S 中有一小群人 T，T 人數(shù)為 3 而 T 中所有 2 人的關(guān)係都屬於同一類，則 S 的人數(shù)至少為 6。圖二中頂點(diǎn) A、B、C、D、E 代表五人，其二人之關(guān)係分為實(shí)線相連的與虛線相連的兩類。很容易看出任意三人其所有 2 人的關(guān)係不可能屬於同一類。 圖二 2.2. 蘭姆西定理為敘述方便，集合 S 的子集 T 若具有 l 個(gè)元素我們稱 T 為 S 的 l-子集。蘭姆西定理是說(shuō) 蘭姆西定理： 給定正整數(shù) l 及不小於 l 之 t 個(gè)整數(shù) q1,q2,qt， 則存在一最小整數(shù) 使得對(duì)任意元素個(gè)數(shù) 的集合 S 都具有以下性質(zhì)： 如果對(duì)

12、 S 中所有 l-子集任意以數(shù)字 進(jìn)行標(biāo)號(hào)， 則 S 中必定有子集 T， 其元素個(gè)數(shù)為某一 qk 且所有 T 之 l-子集都標(biāo)號(hào)碼 。 當(dāng) l=2, t=2, q1 = q2 = 3 時(shí) N(q1,q2;l) = 6 即為上一節(jié)所舉的例子。當(dāng) l=1 時(shí) 即是鴿籠原理。 蘭姆西定理可以說(shuō)是將鴿籠原理從裝 1-子集的籠子推廣到裝一般 l-子集的籠子。 稱為蘭姆西數(shù)，一般情形蘭姆西數(shù)並不能寫成 q1, q2,qt 及 t 的整齊形式，這也是此定理難說(shuō)、難懂的原因。蘭姆西數(shù)由定理可知是確定存在的，但到底為何數(shù)，所知極少。譬如 蘭姆西定理的證明運(yùn)用數(shù)學(xué)歸納法，雖巧妙但稍微繁複，在此從略。有興趣的讀者請(qǐng)

13、參看文後參考文獻(xiàn)。 為了使讀者對(duì)蘭姆西定理有比較具體的形象，我們用以下不太精確的語(yǔ)言再加說(shuō)明?？紤] l=20，q1=50，q2=10 的情形。定理告訴我們蘭姆西數(shù) N(50,100;20) 存在，但 N(50,100;20) 確為何數(shù)並不知道，姑且當(dāng)它為1000好了。 S 是一個(gè)點(diǎn)數(shù)大於或等於1000的集合，將 S 中所有20點(diǎn)的集合分為黑與白兩類。那麼，S 中一定有一個(gè)子集 T 滿足下列二條件之一： (1) T 共有50點(diǎn)且 T 之所有20點(diǎn)的子集（此種子集的個(gè)數(shù)有 個(gè)）都是黑的。 (2) T 共有100點(diǎn)且 T 之所有20點(diǎn)的子集（此種子集的個(gè)數(shù)有 個(gè)）都是白的。 2.3. 平面上之凸多邊

14、形平面上四點(diǎn)，雖無(wú)三點(diǎn)共線，但不一定構(gòu)成凸四邊形，然而點(diǎn)數(shù)超過(guò)四點(diǎn)必定其中有四點(diǎn)構(gòu)成凸四邊形。我們將在此給予更一般性的證明作為蘭姆西定理應(yīng)用之一例。 定理： 對(duì)任意 的整數(shù)，可找到正整數(shù) N(m)。 若 ， 平面上無(wú)三點(diǎn)共線的任意 n 點(diǎn)中必定有 m 點(diǎn)構(gòu)成凸 m 邊形。 借用兩個(gè)事實(shí)作為引理。 引理1：平面上有五點(diǎn)，其中任意三點(diǎn)不共線，則五點(diǎn)中必有四點(diǎn)構(gòu)成凸四邊形。 引理2：平面上有 m 點(diǎn)，其中任意三點(diǎn)不共線，但任意四點(diǎn)構(gòu)成凸四邊形，則此 m 點(diǎn)構(gòu)成凸 m 邊形。 定理的證明如下： 將平面上所有四點(diǎn)的集合分為兩類 S1 及 S2。四點(diǎn)構(gòu)成凸四邊形者屬於 S1；四點(diǎn)構(gòu)成凹四邊形者屬於 S2。

15、設(shè)定 q1 = m，q2 = 5 及 l=4，則蘭姆西數(shù) N(m,5;4) 存在。令 N(m) = N(m,5;4)。若 ， 平面上 n 點(diǎn)的集合 S，其中無(wú)三點(diǎn)共線者必含有一子集 T 滿足(i) T 具有 m 點(diǎn)且 T 之任四點(diǎn)構(gòu)成凸四邊形，或滿足(ii) T 具有 5 點(diǎn)且 T 之任四點(diǎn)構(gòu)成凹四邊形。但由引理 1， (ii)之發(fā)生為不可能，故 T 滿足(i)。由引理 2 得知 T 構(gòu)成凸 m 邊形，定理得證。 N(m) 之存在已證明確定，但 N(m) 確為何數(shù)與蘭姆西數(shù)一樣所知無(wú)幾。例如 N(4)=5, N(5)=9 但 就不知道了。有人猜測(cè) N(m)= 2m-2 +1 ，對(duì)此至今尚無(wú)證明

16、或反證。 2.4. 圖形學(xué)觀點(diǎn)看蘭姆西定理圖形學(xué)(Graph theory) 是組合理論很重要的一分支。很多非連續(xù)模型 (Discrete model) 都可用圖形 (graph) 來(lái)描述。所謂的圖形是指一個(gè)有限集合 V 及 V 中之一些 2-子集 E。V 中之元素稱為點(diǎn)， E 中之元素稱為線。普通記為 G= (V,E)，稱 G 為一圖形 (graph)。若 (x,y) 為 E 中元素，則稱點(diǎn) x 與點(diǎn) y 相鄰或點(diǎn) x 與點(diǎn) y 有關(guān)聯(lián)。以下圖三都是圖形簡(jiǎn)單的例子。圖三中以代表屬於 V 之點(diǎn)，兩點(diǎn)間若有線相連則此兩點(diǎn)構(gòu)成的 2-子集屬於 E。 圖三 結(jié)構(gòu)最簡(jiǎn)單的圖形為 E 等於空集合或 E

17、等於所有 V 之 2-子集。前者稱為無(wú)趣圖形，後者稱為完整圖形。完整圖形之點(diǎn)數(shù)有 p 個(gè)時(shí)稱該圖形為 p 階完整圖形，記為 Kp 圖三中前三個(gè)圖形各為2階，3階，4階的完整圖形。對(duì)任一圖形 G=(V,E)，我們可以考慮其互補(bǔ)圖形 ， 此中，V' = V 及 E' = 所有 V 之 2-子集扣除 E。圖三中最後兩個(gè)圖形互補(bǔ)。 給定一個(gè)圖形 G=(V,E)，很自然將 V 之所有 2-子集分為二類 S1 = E。及 S2 = X-E。p 及 q 為不小於 2 之整數(shù)。若 G 之點(diǎn)數(shù) 時(shí)，V 中有子集 T 滿足 (i) T有 p 點(diǎn)且T之所有 2-子集屬於 S1，或滿足(ii) T 有

18、 q 點(diǎn)且 T 之所有 2-子集屬於 S2。換言之， (i) 發(fā)生時(shí) T 為 Kp； (ii) 發(fā)生時(shí) 為 Kq。 因此蘭姆西定理以圖形學(xué)之觀點(diǎn)是說(shuō)： 對(duì)任意給定不小於 2 之整數(shù) p 及 q 必有一正整數(shù) N(p,q;2) 存在。任意圖形 G，只要其點(diǎn)數(shù) ， 必然 G 包含 Kp 或 包含 Kq。 例如，知道 N(3,6;2)=18。這表示點(diǎn)數(shù) 17 以上的圖形必然有 3 點(diǎn)，兩兩有線相連；或有 6 點(diǎn)，兩兩無(wú)線相連。 III. 鴿籠原理的挑戰(zhàn)善用鴿籠原理常有奇妙驚人的結(jié)果，各位讀者，你是不是也想一顯身手，以下是鴿籠原理對(duì)你的挑戰(zhàn)。 §3.1. 任意 52個(gè)整數(shù)中，必定可以選取2個(gè)，使得其和或其差為 100 的倍數(shù)。 §3.2. 在邊長(zhǎng)為1的正三角形上有十點(diǎn)，則必定有二點(diǎn)其距離至大為 。 §3.3. 從 1 到 2n 的 2n 個(gè)自然數(shù)中任取 n+1 個(gè)數(shù)，必定有二數(shù)其一為另一的倍數(shù)或因數(shù)。 §3.4. 阿德今年高三畢業(yè)，距離大專聯(lián)考尚有37天。為了有效支配時(shí)間，他決定每天最少用1小時(shí)，總共用60小時(shí)準(zhǔn)備數(shù)學(xué)科目的綜合溫習(xí)。不管阿德如何安排他的時(shí)間表（時(shí)間表以小時(shí)為單位），在一段連續(xù)的日子裡，阿德將花 13 小時(shí)在溫習(xí)數(shù)學(xué)上。 §3.5