鴿籠原理

　1│2│3　

首頁 | 搜尋

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

鴿籠原理

謝聰智

I. 鴿籠原理
II. 三個知友或三個陌生人
III. 鴿籠原理的挑戰

I. 鴿籠原理

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

對外搜尋關鍵字：
．鴿籠原理
．Erdos
．Ramsey
．蘭姆西定理
．圖形學

1.1. 連勝 21 次的圍棋高手

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

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

設 s₁, s₂,…,s₇₇ 等為第 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)

s₁, s₂,…,s₇₇ 及 t₁, t₂,…,t₇₇ 共有154個數，但其值落在 1 至153之153個數中。由鴿籠原理，其中必有二個數其值相同。由(1)及(3)，s_i 之間彼此不相等，t_j 之間亦彼此不相等。因此某一 s_k 等於某一 t_l。此即 s_k = t_l = s_l +21 或 s_k - s_l = 21。換言之，從第 l+1 天至第 k 天，沈棋士不多不少勝了21次。

1.2. 園遊會中好友知多少

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

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

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

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

a₁,a₂,…,a_n，為給定之 n 個正整數列，設

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

以 n 除 s_j 得商 q_j，餘 r_j 寫成

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

若某一 r_k=0 則 s_k 為 n 之倍數即得結論，因此假定所有 $r_i \neq 0$ , j=1,2,…,n，則 r₁,r₂,…,r_n 等 n 個數，其值皆落在 1,2,…,n-1 等之 n-1 個數中，由鴿籠原理，必有某一 r_k 等於某一 r_i。故 s_l-s_k 為 n 之倍數。此即說

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

可被 n 除盡。

1.4. 十人中之高矮次序

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

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

m₁,m₂,…,m_n²+1 為 n² +1 個數，其值落在 1,2,…,n 之 n 個數中，由鴿籠原理，必有 n+1 個 m_i 取同一值。令

$\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}$ 則 a_i₁ 接上以 a_i₂ 為起點之最長遞增序列構成以 a_i₁ 為起點，長度為 m_i₂+1 之遞增子序列，因此 $m_{i_2} +1 \leq m_{i_1}$ 。此與(4)式矛盾，故 a_i₁ > a_i₂，同理 a_i₂ > a_i₃, … $a_{i_n}\leq a_{i_{n+1}}$ 等。此即 a_i₁,a_i₂, … a_{i_n+1} 是長度為 n+1 之遞減子序列。

1.5. 101個數中的奇蹟

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

任意選取之 101 個數記為 a₁,a₂, …, a₁₀₁。將 a_i 中所有含 2 之因數刮出，寫成

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

其中 p_i 為奇數。 p₁, p₂,…,p₁₀₁ 等 101 個數，其值落在 1,3,5,… ,199 等之 100 個數中。由鴿籠原理，知道某兩個 p_i 相等。設 p_k = p_l = p 則 a_k = 2^t_k p 及 a_l = 2^t_l p，令 s = a_k, 及 t = a_l，則 s,t 滿足所要的條件。

1.6. 圓盤上之七點

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

將圓盤如圖一分成六塊相等之扇形 A₁ O A₂ ,A₂ O A₃,… , A₆ O A₁ 等。令

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

圖一

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

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

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

令 O 點為正三角形的中心，O、A、B、C 中任意兩點的距離都大於或等於 $\frac{1}{\sqrt{3}}$ 。視 O、A、B、C 四點為鴿， S₁、S₂、S₃ 為籠，由鴿籠原理，某一 S_k 包含此四點之兩點。因此 S_k 之直徑大於或等於 $\frac{1}{\sqrt{3}}$ 。

1.8. 廣義的鴿籠原理

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

$\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$ 時即為原來的鴿籠原理。

　1│2│3　


	（若有指正、疑問……，可以在此留言或寫信給我們。）

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

編輯：康明軒

最後修改日期：4/26/2002