已在第一頁 123 次頁

 


首頁 | 搜尋

.原載於數學傳播第二卷第四期
.作者當時任教於中央大學數學系
 

鴿籠原理

謝聰智

 
 


I. 鴿籠原理

鴿籠原理是說k 個東西分成 n 類, 若 $k \geq nr-n+1$ 則有一類東西之數目大於或等於 r。 十隻鴿子分放在九個籠中,必有一籠至少放二隻鴿子。 五房客四房間,一定有二房客共一房間。三男追二女,必有二男為情敵。 十三人同行,必有二人同月生。五人分十六本書,必然有人至少獨得四本書。 這些都是鴿籠原理在生活中常碰到的實例。這樣平凡的道理人人在諸多待人接物中,不假思索屢用不爽。道理雖然簡單,巧妙地運用卻有意想不到的驚奇結果。

 
對外搜尋關鍵字:
鴿籠原理
Erdos
Ramsey
蘭姆西定理
圖形學
 
1.1. 連勝 21 次的圍棋高手

沈士海是位圍棋新秀,去年參加全國圍棋名人大賽,從地方初選到最後名人爭奪戰,一連比賽了11星期。沈高手之戰績輝煌,優勝記錄是:每日至少勝一次;每星期最多勝12次。由此記錄可推得在一段連續的日子堙A沈棋士不多不少連勝了21次。

結論似乎有點出奇。想一想,再看下面的證明。

s1, s2,…,s77 等為第 1 天,第 2 天,……最後第77天沈高手勝棋的累積數。由於每天至少勝一次及每星期最多勝12次,得

\begin{displaymath}
& 1\leq s_1 < s_2 < \cdots < s_{77} \leq 12 \times 11 = 132 &
\end{displaymath} (1)


\begin{displaymath}
& t_i = s_i + 21, \qquad i=1,2,\cdots,77 &
\end{displaymath} (2)


\begin{displaymath}
& 22 \leq t_2 < \cdots < t_{77} \leq 153 &
\end{displaymath} (3)

s1, s2,…,s77t1, t2,…,t77 共有154個數,但其值落在 1 至153之153個數中。由鴿籠原理,其中必有二個數其值相同。由(1)及(3),si 之間彼此不相等,tj 之間亦彼此不相等。 因此某一 sk 等於某一 tl。此即 sk = tl = sl +21sk - sl = 21。換言之,從第 l+1 天至第 k 天,沈棋士不多不少勝了21次。

   
 
1.2. 園遊會中好友知多少

前日學校舉辦園遊會,我帶著妻子兒女參加。那天晴空萬里,人山人海,熱鬧非常。節目精彩,有吃有玩,孩子們格外高興。 正巧碰到一位多年不見的老朋友談笑言歡話當年,卻將妻子冷落在一旁,妻有意提醒似的朝我問:「聽說這麼多人中有兩人相識的朋友一樣多你信不信?」 原來妻子精通鴿龍原理,有意考我。好在我在這方面也不是弱者,略加思索,我得出一般的推論: 「一群人中必有兩人各有一樣多的知友」。 各位讀者,你認為這結論對嗎?想一想,再看下面的證明。

今有人數為 n 的一群人 SS 可分為 A0, A1,…, An-1。 此中 Ai 表示 S 中有 i 個朋友的那些人。 視 ai 為鴿,Ai 為籠。在此 n 鴿 n 籠,鴿籠原理得不出結論, 但稍加注意就可看出 A0An-1 中必有一籠是空的。若 A0 不空, 表示有一人跟其他所有人都不是朋友,因此沒有一人認識所有其他 n-1 人, 此即表示 An-1,是空的;若 An-1, 不空表示有一人認識所有其他 n-1 人,因此不可能有一人跟其他所有人都不是朋友,此即表示 A0 是空的。故或 A0An-1 為空, 不管如何,S 事實上分為 n-1 類。 由鴿籠原理,有一類至少有二人。換言之,有二人各有一樣多的朋友。

   
 
1.3. 科學小飛俠的紙牌遊戲

小飛俠一號鐵雄與三號珍珍,在掃蕩惡魔黨之餘暇,常愛玩一種鬥智的紙牌遊戲。遊戲開始前,兩人各準備五張空白的紙牌,各按自己的意思在每張牌上寫一個號碼,然後各自將五張寫上號碼的牌與對方交換。 遊戲開始,兩人猜拳決定先後秩序輪流出一張牌。當出手之牌與桌面上適當挑選的牌加起來,其點數和為10之倍數時,出牌者得勝,比賽結束;否則輪到對方出牌繼續比賽。若最後各人把百張牌出完而未分勝負,比賽即為雙和。這遊戲既簡單又有趣,鐵雄與珍珍玩得津津有味。但很奇怪,玩了千百次的記錄中,各有勝負,但從來沒有雙和的情況發生。 有一次,他們就把這遊戲是否有雙和的問題請教南宮博士。他思索片刻,洞察其中道理後說:「是的,十個任意數目統統加起來若不是十的倍數,其中必有一部份加起可被十除盡」。接著南宮博士又說:「事實上,任意給定 n 個正整數的數列 a1, a2,…,an,必定有一段連加起來是 n 的倍數。用鴿籠原理試證明看」。 小飛俠鐵雄不僅武功非凡,智力亦高,經南宮博士一提醒,花了一天一夜苦思,果然看透了問題並想出了證明。各位讀者,想一想,再看以下鐵雄的證明。

a1,a2,…,an,為給定之 n 個正整數列,設

\begin{displaymath}
s_j = a_1 + a_2 + \cdots + a_j, \quad j=1,2,\cdots ,n
\end{displaymath}

nsj 得商 qj,餘 rj 寫成

\begin{displaymath}
s_j = nq_j + r_j, \qquad 0 \leq r_j \leq n-1, \qquad j=1,2,\cdots,n
\end{displaymath}

若某一 rk=0skn 之倍數即得結論,因此假定所有 $r_i \neq 0$, j=1,2,…,n,則 r1,r2,…,rnn 個數, 其值皆落在 1,2,…,n-1 等之 n-1 個數中, 由鴿籠原理,必有某一 rk 等於某一 ri。 故 sl-skn 之倍數。此即說

\begin{displaymath}
a_{k+1} + a_{k+2} + \cdots + a_{l}
\end{displaymath}

可被 n 除盡。

   
 
1.4. 十人中之高矮次序

十個人任意排成一列必定有四人是按高矮順序排列。 事實上,一般的情形,任意長度為 n2+1 之實數敘列必包含有 n+1 長度為 n+1 之遞增或遞減子敘列。 下面是組合學大師耶迪西 (Erdös) 的證明。 假設給定之實數敘列 a1,a2,…,an2+1 中沒有長度為 n+1 的遞增子敘列, 我們將證明必定有長度為 n+1 之遞減子敘列。 對任意 ai 考慮所有以 ai 為起點之遞增子敘列。 令 mi 為此種遞增子敘列中可能達到之最大長度。由開始的假定得

\begin{displaymath}
1\leq m_i \leq n , \qquad i=1,2, \cdots ,n^2+1
\end{displaymath}

m1,m2,…,mn2+1n2 +1 個數, 其值落在 1,2,…,nn 個數中,由鴿籠原理, 必有 n+1mi 取同一值。令
\begin{displaymath}
m_{i_1}=m_{i_2}=\cdots =m_{i_{n+1}} \quad \mbox{{\fontfamily...
...ntseries{m}\selectfont \char 47}} \quad i_1<i_2<\cdots<i_{n+1}
\end{displaymath} (4)

$a_{i_1}\leq a_{i_2}$ai1 接上以 ai2 為起點之最長遞增序列構成以 ai1 為起點, 長度為 mi2+1 之遞增子序列,因此 $m_{i_2} +1 \leq m_{i_1}$。 此與(4)式矛盾,故 ai1 > ai2,同理 ai2 > ai3, … $a_{i_n}\leq a_{i_{n+1}}$ 等。此即 ai1,ai2, … ain+1 是長度為 n+1 之遞減子序列。

   
 
1.5. 101個數中的奇蹟

從 1、2、3、……、200 的二百個數中任取 101 個數則其中必定有二數 s,t,使得 st 的因數或 ts 的因數。 想一想,再看以下的證明。

任意選取之 101 個數記為 a1,a2, …, a101。 將 ai 中所有含 2 之因數刮出,寫成

\begin{displaymath}
a_i = 2^{l_i}p_i, \quad i=1,2,3,\cdots,101
\end{displaymath}

其中 pi 為奇數。 p1, p2,…,p101 等 101 個數, 其值落在 1,3,5,… ,199 等之 100 個數中。 由鴿籠原理,知道某兩個 pi 相等。設 pk = pl = pak = 2tk pal = 2tl p,令 s = ak, 及 t = al,則 s,t 滿足所要的條件。

   
 
1.6. 圓盤上之七點

半徑為 1 的圓盤上有七點,其中任意二點的距離都不小於 1。 則七點中有一點為圓心。結論有點出奇,想一想,再看以下證明。

將圓盤如圖一分成六塊相等之扇形 A1 O A2 ,A2 O A3,… , A6 O A1 等。令

\begin{displaymath}
\begin{array}{l}
S_1 = \mbox{{\fontfamily{cwM5}\fontseries{m...
...fontfamily{cwM0}\fontseries{m}\selectfont \char 1}}
\end{array}\end{displaymath}



圖一

除圓心外,圓盤上之任一點都屬同而僅屬於某一Si 。 若七點中無一為圓心,則其中有二點屬於同一 Si。但 Si 中之任意二點的距離都小於1,故不可能七點中無一點為圓心。結論確定。

   
 
1.7. 正三角形內之三個區域

正三角形 ABC 各邊長為 1, 將 ABC 所圍成的點集合,任意分成 S1,S2,S3 三區域, 則必定有某一 Si 之直徑大於或等於 $\frac{1}{\sqrt{3}}$ 了。 此中所謂點集合 S 的直徑是指 S 中任意兩點距離的最大數。 由於 S1,S2,S3 之形狀毫無限制,初看,問題是似乎很難, 想一想,再看以下的證明。

O 點為正三角形的中心,OABC 中任意兩點的距離都大於或等於 $\frac{1}{\sqrt{3}}$。視 OABC 四點為鴿, S1S2S3 為籠,由鴿籠原理,某一 Sk 包含此四點之兩點。 因此 Sk 之直徑大於或等於 $\frac{1}{\sqrt{3}}$

   
 
1.8. 廣義的鴿籠原理

給定非負的整數 q1, q2,…,qn,將 k 個東西分為 n 類, 若 $k \leq q_1 + q_2 + \cdots\cdots + q_n -n +1$ 則一定有某第 i 類東西個數大於或等於 qi 個。 這是鴿籠原理一般情況。它的證明很簡單,假若結論不確,即是說第 1 類東西小於 q1,第 2 類小於 q2,……第 n 類小於 qn。 則所有東西總和

\begin{displaymath}
k \leq (q_1 -1) + (q_2 -1) + \cdots \cdots + (q_n -1)
= q_1 + q_2 + \cdots \cdots + q_n -n
\end{displaymath}

此與前提矛盾故不可能。 當 $q_1 = q_2 = q_3 = \cdots\cdots = r$ 時即為原來的鴿籠原理。

   

已在第一頁 123 次頁

回頁首
 
(若有指正、疑問……,可以在此 留言寫信 給我們。)
EpisteMath

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有


編輯:康明軒 最後修改日期:4/26/2002