遊戲規則：本遊戲為猜密碼的遊戲。密碼為0到100之間的其中1個整數，電腦會提示密碼的所在範圍，玩家必須在6次之內猜到密碼才能過關。
★ 終極密碼為0到100之間 ★
您共有六次機會
摘要. 1932年 Klein 提出這樣的問題: 對於給定的正整數 $n$, 能否找到一個正整數 $N(n)$, 使得平面上任意 $N(n)$ 點 (其中任三點不共線) 中, 均能找到 $n$ 點形成凸多邊形。 本文首先介紹這個被 Erdös 稱為「幸福結局問題」的來龍去脈, 並討論鴿籠原理與拉姆西定理, 及他們如何應用在這個問題上。
匈牙利數學奇才 Paul Erdös 於1996年9月24日以八十三歲高齡去世, 他一生寫過的學術論文達1475篇, 不只數目多, 而且分量紮實, 其中有許多影響後來的發展甚深。 現在要談的是他年輕時和 Szekeres 合力解決 Klein 提出來的一個平面幾何問題的一段歷史, 以及其後的影響。
Erdös 於1913年3月26日出生在匈牙利, 自小就已顯露其數學才能。 1930年代初, Erdös 和一些年輕數學家們每週聚會一次, 一起聊天、談論時事, 尤其是研討數學。 週日他們去布達佩斯郊外爬山越嶺, 也常在城市公園裡披斗篷的無名者青銅像下的長椅上聚會。
在無名者銅像下, Erdös 和他的夥伴們有關政治和家庭的話題, 總是不如數學多。 他們沉迷於數學, 其中尤以 Erdös 最為癡迷, 他的熱衷數學, 很能帶動同伴們的討論。
1932年歲末, 在無名者銅像下聚會的人群中多了 Esther Klein, 她是一個在哥廷根大學唸了一學期, 中途跑出來, 頗有才華的學生, 還有 Gyorgy Szekeres, 他是一個急於把試管拋掉而投身數學的化學系畢業生。
有一次, 在他們每週的活動中, Klein 提出一個希奇古怪的平面幾何問題: 平面上給定五點, 若任意三點不共線, 求證必有四點構成凸四邊形。 (一個四邊形是由四條只交在端點的邊構成的圖形, 正方形、矩形、平行四邊形和梯形都是四邊形; 同理可以有五邊形、 $n$ 邊形等多邊形。 至於「凸」是指從多邊形內部任意一點都可以直接「看到」另外一點, 也就是, 凸多邊形內部任意兩點的連線仍在該多邊形內部; 所以正方形是凸四邊形, 而成箭頭狀的四邊形不是凸四邊形, 因為位於一側箭尾的點不能直接「看到」位於另一側箭尾的點。)
Klein 證明平面上任意三點都不共線的五點, 不外乎下面三種情況, 而每種情況下都保證能構成一個凸四邊形, 定理從而得證。
第一種情況是五點自身就構成一個凸五邊形, 其中任意四點均構成凸四邊形。
第二種情況是其中一點為其餘四點所包圍, 則外部四點構成凸四邊形。
第三種情況是其中兩點位於其餘三點所構成的三角形內部。 若作一直線通過這兩點, 則該直線將三角形分為兩部分, 必有兩個頂點位於直線的一端, 那麼這兩頂點與原來的兩點構成凸四邊形。
大家都很喜歡 Klein 這個簡練的證明, 於是想要將證明推廣到構成更多邊的凸多邊形。 更精確的來說, Klein 建議一個這樣的問題:
|
對於給定的正整數 $n$, 能否找到一個正整數 $N(n)$, 使得平面上任意 $N(n)$ 點 (其中任三點不共線) 中, 均能找到 $n$ 點形成凸多邊形? |
這個問題包括兩件事情, 首先, 這樣的 $N(n)$ 是否一定存在? 其次, 如果存在, 那麼最小的 $N(n)$ 是多少? 為了方便, 我們用 $N_0(n)$ 表示這個最小正整數。 很顯然的 $N_0(3)=3$; 而 Klein 的證明, 再加上一個很簡單的例子 (三角形的三個頂點及內部一點不構成凸四邊形), 就可以得到 $N_0(4)=5$。
在他們這一群人中, 另一名數學家 Endre Makai 很快就證明了 $N_0(5)=9$; 也就是說, 平面上任意三點不共線的任9點中, 一定能找出5點構成凸五邊形, 而且下面的例子顯示8點是不夠的:
由於知道 $N_0(3)=2+1$, $N_0(4)=2^2+1$, $N_0(5)=2^3+1$, 他們動了 $N_0(n)=2^{n-2}+1$ 的腦筋。 過了一陣子他們就意識到, 只靠簡單的論證並無濟於事, 於是圈子裡引發出一股急於解決這個問題的激奮情緒。 對 Szekeres 來說, 解題的動機主要來自 Klein, 獲得佳人青睞強烈地激勵他爭取率先提出解法, 幾個星期後他就面帶勝利的笑容對 Erdös 說: 「E.~P. * * E.~P.~係 Erdös Paul 的縮寫, 和中國人一樣, 匈牙利人的姓是寫在前面的。 , 敞開你那充滿智慧的大腦吧!」 Szekeres 找出了保證可構成凸n邊形的所需點數, 但這個數目比他們猜想的 $2^{n-2}+1$ 大很多; 儘管如此, 他的證明還是贏得了 Klein 的芳心, 四年後有情人終成眷屬。 從此 Erdös 把這個問題稱為「幸福結局問題」, 永垂數學史。
Szekeres 的證明隱含了拉姆西定理, 事實上, 拉姆西定理大約在這五年之前提出來, Szekeres 可以說是在不知情的狀況下獨立重新發展出拉姆西定理。 用後面將介紹的符號表示, 他得到 $$N_0(n) \le R(n, 5; 4).$$ 這個上界其實很大, 後來 Erdös 提出一個更好的上界, 證到 $$2^{n-2} + 1 \le N_0(n) \le {2n-4\choose n-2} +1.$$ 這一次, 上界小了很多, 但利用 Sterling 公式 $$n!\sim \sqrt{2\pi n} \Big({n\over e}\Big)^n,$$ 我們可以得到 $${2n-4\choose n-2} = {(2n-4)!\over (n-2)!(n-2)!} \sim {2^{2n-4}\over \sqrt{\pi(n-2)}},$$ Erdös 得到的上界和下界 $2^{n-2}+1$ 還是有一大段距離。 他們兩人將上述的結果合寫了一篇文章, 1935年發表[1]。 遺留至今還有下面這個未解的問題。
| 猜想: $N_0(n)=2^{n-2}+1$。 |
不管是拉姆西定理的證明, 或者是 Erdös 的改良上界的證明, 都奠基於一個更基礎的道理, 叫做鴿籠原理。 接下來, 我們要來介紹鴿籠原理與拉姆西定理, 並且看看他們如何用來證明 $N_0(n)$ 的上界。
假定有 $n+1$ 隻鴿子和 $n$ 個鳥籠, 如果要讓所有鴿子飛入籠中, 則存在某一個籠子裡面至少有兩隻鴿子。
這個看起來很簡單的原理俗稱鴿籠原理, 也稱抽屜原理, 是十九世紀德國數學家 Dirichlet 提出來, 以解決數論上的一些問題, 所以也有人將它稱為 Dirichlet (抽屜) 原理。
這個貌不驚人的原理, 卻有廣泛而出人意表的許多應用, 有很多很深的定理都可以用它來證明。 在本文末的附錄裡我們收集了各式各樣深淺不一的題目, 它們都能靠鴿籠原理來解決。 這裡我們舉幾個例子來說明。
首先登場的是數論上的定理 (參見[2])。
定理1: 若 $x$ 是一個無理數, 且 $n$ 為正整數, 則存在某個有理數 $h/k$, 其分母 $k\le n$, 滿足 $$\Big|x-{h\over k}\Big|\lt {1\over kn}.$$
證明: 對任一實數 $y$, 我們用 $[y]$ 表示 $y$ 的整數部分, 也就是滿足 $m\le y\lt m+1$ 的唯一整數 $m$。
因為 $x$ 是無理數, 對於 $i=1, 2,\ldots,n$ 恆有 $0\lt ix-[ix]\lt 1$, 也就是說, 我們有 $n$ 個在開區間 $(0,1)$ 的無理數 $ix-[ix]$; 其實每一個這樣的數也一定在下面這 $n$ 個子區間之一: $(0,1/n)$, $(1/n, 2/n),\ldots, ((n-1)/n, 1)$。
如果有某一個 $jx-[jx]$ 在子區間 $(0, 1/n)$ 內, 則我們可以取 $h=[jx]$ 和 $k=j$, 定理就成立。 如果所有這 $n$ 個無理數 $ix-[ix]$ 都落在除了 $(0, 1/n)$ 以外的 $n-1$ 個子區間, 則由鴿籠原理, 存在某一子區間 $(r/n, (r+1)/n)$ 包含某兩個數 $sx-[sx]$ 和 $tx-[tx]$, 其中 $1\le s\lt t\le n$, 這兩個數差的絕對值一定小於 $1/n$, 也就是說 $|(tx-[tx])-(sx-[sx])|\lt 1/n$, 這時可取 $h=[tx]-[sx]$ 和 $k=t-s$, 定理就成立。 $\blacksquare$
接下來, 再來看一組數論上的題目 (參見[3])。
首先我們來證明(甲), 令選出來的數為 $$x_i= 2^{a_i} y_i,$$ 其中 $a_i$ 為非負整數, $y_i$ 為介於1到200之間的奇數, $i=1,2,\ldots, 101$。 因為介於1到200間的奇數只有100個, 根據鴿籠原理, 存在 $i\not=j$ 使得 $y_i=y_j$, 因此, 當 $a_i\ge a_j$ 時 $x_i$ 整除 $x_j$, 當 $a_i\lt a_j$ 時 $x_j$ 整除 $x_i$。 所以 (甲) 得證。
(乙) 只是在說明 (甲) 中的101是不可以再少的。 選 $101,102,\ldots,200$ 這100個數就可以達到目的。
最後考慮 (丙), 假設選出來的100個數是 $$z_i= 2^{b_i}w_i,$$ 其中 $b_i$ 是非負整數, $w_i$ 為奇數, $i=1,2,\ldots,100$。 如果不存在某個 $z_i$ 整除另一個 $z_j$, 則一定有下述性質: $$\hbox{若 } i\not=j \hbox{ 且 } w_i \hbox{ 整除 } w_j, \ \ \hbox{則 }b_i\gt b_j\hbox{。}{(*)}$$
因此, 這100個奇數 $w_i$ 必定都相異。 假設選出來小於16的數是 $2^bw$, 則有下列4種可能:
以上的問題被 [4] 推廣到更一般的情況。
在真正證明 ${2n-4\choose n-2}+1$ 這個 $N_0(n)$ 的上界之前, Erdös 先用鴿籠原理證明了一個類似的定理。
定理 2: 對任一含有 $nm+1$ 項相異實數的數列 $x_1, x_2,\ldots, x_{nm+1}$, 或者存在一含 $n+1$ 項的遞增子數列, 或者存在一含 $m+1$ 項的遞減子數列。
證明: 對應於每一個 $x_j$, 令 $a_j$ 表示以 $x_j$ 為末項的遞增子數列最多的項數, $b_j$ 表示以 $x_j$ 為末項的遞減子數列最多的項數。 對於 $i\lt j$, 當 $x_i\lt x_j$ 時 $a_i+1\le a_j$, 當 $x_i\gt x_j$ 時 $b_i+1 \le b_j$, 因此序對 $(a_i, b_i)\not= (a_j, b_j)$。 因為有 $nm$ 個 $x_j$, 由鴿籠原理可知, 不可能所有 $a_j \le n$ 及所有 $b_j \le m$, 也就是, 或者存在一含 $n+1$ 項的遞增子數列, 或者存在一含 $m+1$ 項的遞減子數列。 $\blacksquare$
利用和這個相類似的論證, 事實上其中也隱含有證明拉姆西定理的精神, Erdös 進一步證明了下面的定理。
定理 3: 當 $m$, $n \ge 2$ 時, 平面上給定 ${n+m-4\choose n-2}$ 點, 假設任三點不共線, 任兩點的橫座標均相異。 則或者存在 $n$ 點 $x_1,x_2,\ldots,x_n$ (橫座標由小而大) , 其連續線段 $x_ix_{i+1}$ 的斜率遞增, 或者存在 $m$ 點其連續線段的斜率遞減。
證明: 令 $f(n, m)$ 表示平面上最多的點數, 使得不存在 $n$-杯 ($n$ 點使得連續線段斜率遞增) , 而且不存在 $m$-帽 ($m$ 點使得連續線段斜率遞減)。 我們首先要證明 $$f(n, m) \le f(n, m-1) +f(n-1, m). {(*)}$$
設 $S$ 是有 $f(n, m)$ 點但無 $n$-杯無 $m$-帽的點集, 令 $T$ 是所有可為 $(n-1)$-杯右端點的集合, 則 $S\setminus T$ 中沒有 $(n-1)$-杯也沒有 $m$-帽, 所以 $$|S\setminus T| \le f(n-1, m).$$ 再者, 如果 $T$ 中有一個 $(m-1)$-帽 $A$, 令其左端點為 $x$, 左邊倒數第二點為$y$, 由 $T$ 的定義, $x$ 是某一 $(n-1)$-杯 $B$ 的右端點, 令此杯右邊倒數第二點為 $z$; 如果 $zx$ 的斜率小於 $xy$ 的斜率, 則 $B$ 和 $y$ 合成 $n$-杯; 如果 $zx$ 的斜率大於 $xy$ 的斜率, 則 $z$ 和 $A$ 合成 $m$-帽; 兩種情況都不可能, 所以 $T$ 中沒有 $n$-杯及 $(m-1)$-帽, 因此 $$|T| \le f(n, m-1),$$ 所以 $(*)$ 成立。 此不等式和巴斯卡等式, 再加上數學歸納法可以證明 $f(n, m) \le {n+m-4\choose n-2}$, 所以定理得證。 $\blacksquare$
由定理3再加上適當的選取座標軸, 使得不會有兩點有相同橫座標, 就可以證得 $$N_0(n) \le {2n-4\choose n-2}+1.$$ 至於 $2^{n-2} + 1 \le N_0(n)$, 則要小心地選取反例就可以得到。
雖然 Erdös 的上界比 Szekeres 的上界好, 但因為後者是採用拉姆西數得到的, 這套理論也很值得知道, 再者有感於 Szekeres 是第一個證明 $N(n)$ 確實有限的人, 所以也要來談談他的工作。
鴿籠原理有多種變形, 其中之一是: 假設有 $p_1+p_2+\cdots+ p_n-n+1$ 隻鴿子和 $n$ 個鳥籠, 如果要讓所有鴿子飛入籠子, 則必定存在某個 $i$, 使第 $i$ 個籠子中至少有 $p_i$ 隻鴿子。 當 $p_1=p_2=\cdots=p_n=2$ 就是最原始的鴿籠原理。
拉姆西定理最簡單但還要點證明的情況, 可以用下面的例子說明。 有6個人, 任兩人或者彼此相識, 或者彼此不相識 (但沒有甲認識乙, 而乙不認識甲的情況) , 則必存在兩兩互相認識的3人, 或兩兩互相不認識的3人。
這個事實的證明如下。 首先指定一人, 在其餘5人當中, 他或者與其中3人認識, 或者與3人不認識 (應用鴿籠原理 $5=3+3-2+1$)。 先考慮他與某3人認識的情況, 如果這3人中有某2人互相認識, 則這2人與原來選出的那人, 合成兩兩互相認識的3人; 如果這3人兩兩互相不認識, 上敘述也得證。 選定那人與某3人不認識的情況, 其證明亦類似。
我們也可以將上述的道理用集合的語言寫出來: 假設 $S$ 是一含有6元素的集合, 任意將其所有15個含有2個元素的子集合分成兩類, 則 $S$ 中一定有一恰含3個元素的子集 $T$, 這個子集的任何含2個元素的子集都在同一類。
這樣的寫法, 看起來有點古怪, 但有利於後面的一般化。 先舉一個例子說明如下:
令 $S=\{1, 2, 3, 4, 5, 6\}$。
第1類2元素子集: $\{1, 2\}$, $\{1, 6\}$, $\{2, 3\}$, $\{3, 4\}$, $\{4, 5\}$, $\{5, 6\}$。
第2類2元素子集: $\{1, 3\}$, $\{1, 4\}$, $\{1, 5\}$, $\{2, 4\}$, $\{2, 5\}$, $\{2, 6\}$, $\{3, 5\}$, $\{3, 6\}$, $\{4, 6\}$。
則可以找到 $T=\{1, 3, 5\}$, 其所有2元素子集都是第2類。
拉姆西定理: 假設正整數 $p_1, p_2,\ldots, p_n$, $t$ 滿足 $p_1\ge t, p_2 \ge t,\ldots, p_n \ge t$, 則一定存在一最小正整數 $R(p_1, p_2,\ldots, p_n; t)$ 滿足下面性質: 假設集合 $S$ 至少有 $R(p_1, p_2,\ldots, p_n; t)$ 個元素, 任意將其 $t$ 元素子集分成 $n$ 類, 則必有某一 $i$ $(1 \le i \le n)$ 使得 $S$ 有一恰含 $p_i$ 個元素的子集 $T$, 其所有 $t$ 元素子集都是第 $i$ 類。
利用上述定理的符號, 則上述6人中3人互相認識, 或不認識的事情, 就可以寫成 $R(\hskip -1pt 3,\hskip -1.2pt 3;\hskip -1.2pt 2\hskip -1pt)$ $\le 6$。 事實上, $R(3, 3; 2)=6$, 因為5個人就有可能找不到兩兩認識的3人, 或兩兩不認識的3人。
一般說來, 決定拉姆西數是困難的事。 $t=1$ 就是一般化的鴿籠原理, 也就是 $$R(p_1, p_2,\ldots, p_n; 1) = p_1+p_2+\cdots+ p_n-n+1.$$ 當 $t\ge 2$ 時, 就不容易決定 $R(p_1,p_2,\ldots, p_n; t)$ 了, 縱使是 $R(p, q; 2)$ 都不是那麼容易。 從定義, 倒不難看出 $$R(p, t; t)=R(t, p; t)=p,$$ 所以上述的 $R(3, 3; 2)=6$ 算是第一個要花一點力氣得到的結果。 利用和證明定理3類似的說法, 可以證得 $$R(p, q; 2) \le R(p-1, q; 2) + R(p, q-1; 2),$$ 再加上巴斯卡等式及數學歸納法, 也可以得到 $$R(p, q; 2) \le {p+q-2\choose p-1}.$$
最後讓我們用拉姆西數的符號來說明 Szekeres 的上界。
定理 4: $N_0(n) \le R(n, 5; 4)$。
證明: 假設 $S$ 是平面上 $m=R(n, 5; 4)$ 點所成的集合, 其中任三點都不共線。 我們想證明, $S$ 中存在 $n$ 點, 構成凸 $n$ 邊形。
首先, 將 $S$ 的所有4元素子集分成二類, 第1類是4點成一凸四邊形的子集, 第2類是4點不構成凸四邊形的子集。 由 $R(n, 5; 4)$ 的定義可知: 或者存在 $S$ 的 $n$ 元素子集 $T$, 其任一4元素子集都能構成凸四邊形; 或者存在 $S$ 的5元素子集 $T$, 其任一4元素子集都不構成凸四邊形。 但是 Klein 原來的論證已經說明後者不可能, 所以前者恆成立, 此時, $T$ 中的 $n$ 點必構成一凸 $n$ 邊形。 $\blacksquare$
星起星落, 1930年的激情匆匆已過七十餘年, 當年的一對佳人現在還幸福的住在美國新澤西州, 而才子 Erdös 過世數年。 他們留給後人的是一片大好數學江山, 以及沉迷數學的回憶。 且讓後人續之。 欲知後事如何, 請看 [5, 6, 7]。
2003年2月到4月間, 本文著者應邀到九九文教基金會主辦的 ARML 培訓營、九章講座、數學奧林匹亞訓練營演講, 本文以此為基礎撰寫而成。
| 32, | 1, | 110, | 7, |
| 31, | 109, | 103, | 25, |
| 78, | 6, | 78, | 6, |
| 72, | 72, | 72, | 72, |
| 0, | 0, | 0, | 0. |
---本文作者任教於國立台灣大學數學系---
聯絡方式: 10617 台北市羅斯福路四段1號 天文數學館6樓 中央研究院數學研究所數學傳播編輯部
Tel:02-23685999 轉 382 | Email: media@math.sinica.edu.tw
網路平台: 數學所資訊室 | Tel:02-23685999 轉 743 | Email: ytlin@math.sinica.edu.tw
© 2017 中央研究院數學研究所 All rights reserved.