摘要. 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])。

• (甲) 從1到200的整數中挑出101個數, 證明存在一數整除另外一個。
• (乙) 從1到200的整數中, 試找出100個數, 使得任一數不整除另一個。
• (丙) 從1到200的整數中挑出100個數, 如果至少有一數小於16, 證明存在一數整除另外一個。

首先我們來證明(甲), 令選出來的數為 $$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種可能:

• (1) $b=3$, 此時 $w=1$, 所以 $3^bw=27$。
• (2) $b=2$, 此時 $w\le 3$, 所以 $3^bw \le 27$。
• (3) $b=1$, 此時 $w\le 7$, 所以 $3^bw \le 21$。
• (4) $b=0$, 此時 $w\le 15$, 所以 $3^bw \le 15$。

在任何情況下, $3^bw \le 27$, 所以 $$w\lt 3^1w\lt 3^2w\lt \cdots\lt 3^bw\lt 3^{b+1}w$$ 這 $b+2$ 個奇數均小於200, 因此它們都對應於各個 $w_i$, 或者說, 存在 $b+2$ 個選出來的數形如 $2^bw$, $2^{c_1}3^1w, 2^{c_2}3^2w,\ldots, 2^{c_b}3^bw, 2^{c_{b+1}} 3^{b+1}w$, 由 $(*)$ 可知, $b\gt c_1\gt c_2\gt \cdots\gt c_b\gt c_{b+1}\ge 0$, 因此0和 $b-1$ 之間有 $b+1$ 個相異的整數 $c_1,\ldots,c_{b+1}$, 矛盾。 所以 (丙) 得證。

以上的問題被 [4] 推廣到更一般的情況。

五. Erdös 的巧思

在真正證明 ${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)$ 確實有限的人, 所以也要來談談他的工作。

六. 拉姆西理論及 Szkeres 的證明

鴿籠原理有多種變形, 其中之一是: 假設有 $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 培訓營、九章講座、數學奧林匹亞訓練營演講, 本文以此為基礎撰寫而成。

參考文獻

附錄

• 1.
  • (a) 400個人之中至少有兩人生日同一天。 為什麼?
  • (b) 把400換成另外一數而上面的陳述仍然成立, 此數最小是多少?
  • (c) 要多少人才能保證其中至少有三人生日相同?
  • (d) 要多少人才能保證有不同的兩天都有兩個以上的人作生日?
• 2. 有 $kn+1$ 個球要放進 $n$ 個箱子。 一定會發生什麼事?
• 3. 沒有人的頭髮超過三十萬根, 新竹市的人口是三十萬零一人。 你能斷言新竹市有兩人頭上的毛一樣多嗎?
• 4. 箱子裡有70個球五種顏色: 20個紅, 20個藍, 20個黃, 其餘的10個球有黑有白。
  • (a) 你至少必須拿多少球才能保證拿到10個同色的球?
  • (b) 你至少必須拿多少球才能保證拿到全部五種顏色?
• 5. 媽媽俱樂部有28位太太, 王太太有13個小孩, 其他人都沒她多。
  • (a) 證明至少有三位太太的小孩一樣多。
  • (b) 其他條件不變, 俱樂部中該有多少媽媽才能保證有四位太太的小孩一樣多?
• 6. 客廳裡有 $n$ 個人, 證明他們之中有兩人在客廳中認識的人一樣多。
• 7. 會場中有 $n$ 個專家。 每個人都和其他人正好握一次手。 證明在握手寒喧的這段時間中, 每一時刻都至少有兩個人已經握手的數目相同。
• 8. $n$ 個人參加循環賽, 每個人都要和別人正好比賽一次。 證明在整個賽程中之任一時刻, 至少有兩隊到那時刻為止已經賽完了一樣多場。
• 9. 51隻小昆蟲放置在邊長1的方塊內。 證明無論何時, 至少有三隻昆蟲可以罩在一個半徑 ${1\over 7}$ 的圓內。
• 10. 在平面格子點中選定五個格子點。 證明永遠可以找到其中兩點, 使得它們的連線通過另一格子點。 (格子點是指座標為整數的點。)
• 11. 令 $P_1, P_2,\ldots, P_9$ 為空間中的九個格子點。 證明有一格子點落在某線段 $P_iP_k$ 上, $i\not=k$, $i$, $k\in\{l, 2,\ldots,9\}$。
• 12. 在一個邊長7的正方體內選定342個點。 你能否放置一個邊長1的小正立方體到大立方體內, 使此小正立方體的內部不包含選定的這些點?
• 13. 一個靶其形狀為邊長2的等邊三角形。
  • (a) 如果射中靶五次。 證明有兩個彈孔的距離小於或等於1。
  • (b) 如果射中靶17次。 關於兩個彈孔之間的最小距離能斷言什麼?
• 14. 在數列 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1,$\ldots$ 中每一項都是前兩項之和, 只不過加法是在模10下做的。 證明此數列是週期的。 週期的可能長度最大是多少? 證明週期以 1, 1, 2, 3, 5,$\ldots$ 開始。
• 15. 考慮由 $$a_1=a_2=1,\quad a_{n+1}=a_{n-1}+a_n,\quad n\gt 1,$$ 所定義的費波那奇 (Fibonacci) 數列, 1, 1, 2, 3, 5, 8,$\ldots$。 證明對任一 $n$ 有一費波那奇數尾巴有 $n$ 個零。
• 16. 假定 $a$ 與2及5互質。 證明對任一 $n$, 有一個 $a$ 的乘冪其尾巴是 $\underbrace{000\cdots 01}_n$。
• 17. 有10條線段, 每一條都比一寸長, 比55寸短。 證明可以從中選出三條造出一個三角形。
• 18. 在一間五坪大的房間中放了九塊面積都是一坪的地氈, 地氈的形狀沒有限制。 證明有兩塊地氈至少重疊了 ${1\over 9}$ 坪。
• 19. 從集合 $\{1, 2,\ldots, 2n\}$ 中任選 $n+1$ 個數。 證明在這些選出的數中, 永遠有一對, 大的被小的整除。
• 20. 從集合 $\{1, 2,\ldots, 2n\}$ 中任選 $n+1$ 個數。 證明在這些選出的數中, 至少有一對是互質的。
• 21. 令 $n$ 為一自然數, 不被2或5整除。 證明 $n$ 有一個倍數全由1組成, 即成 $111\cdots 11$ 的形式。
• 22. $S$ 為 $n$ 個自然數的集合。 證明 $S$ 有一個子集合其元素之和被 $n$ 整除。
• 23. 證明在六個人之中永遠有三個人彼此都認識, 或者有三個人彼此全不認識。
• 24. 空間中給了6點, 沒有三點在同一直線上, 每兩點都用直線段連結起來, 每一線段塗成黑色或白色。 證明由這些線段所構成的三角形中, 永遠至少有一個, 它的邊都同色。
• 25. 空間中給了17點, 沒有三點在同一直線上, 每兩點都用直線段連結起來, 每條線段塗上黑色、白色或紅色。 證明有一個三角形它的邊都同色。
• 26. 空間中給了66點, 沒有三點在同一直線上, 每兩點都用直線段連結起來, 線段塗上黑色、白色、紅色或綠色。 證明有一個三角形它的邊都同色。
• 27. 推廣24、 25、 26這一系列的問題。
• 28. $S$ 是一個25個點的集合, 其中任一個3個點的子集合中至少有兩點距離小於1。 證明 $S$ 有一個13個點的子集合可以用半徑1的圓盤覆蓋住。
• 29. 證明在 $a^2+1$ 個東西中, 或者有 $a+1$ 個同一類, 或者有 $a+1$ 個不同類。
• 30.
  • (a) 平面上的點分成兩個子集合。 證明有兩點距離為1且屬於分後的同一子集合中。
  • (b) 平面上的點分成三個子集合。 證明有兩點距離為1且屬於分後的同一子集合中。
  • (c) 將平面分成七個子集合, 使得沒有兩點距離為1且屬於同一子集合。
  • 註: 至於分成4、 5或6個子集合的情況, 沒人知道是否永遠有一子集合包含兩點距離為1。
• 31. 錫金尼亞國的公路系統是這樣的: 在每個交叉路口有三條公路交會。 下圖顯示了這樣一個公路系統的簡單例子。 證明錫金尼亞公路系統的下列性質: 從任一交叉路口 $A_1$ 出發延著三條路中任一條到下一路口 $A_2$ 向右轉開到下一路口 $A_3$。 在 $A_3$ 向左轉, 這樣繼續下去, 一次右轉一次左轉。 那麼你最後會回到出發點 $A_1$。

  

• 32.
  • (a) 證明任一含有 $n^2+1$ 項的實數列, 必有一長度 $n+1$ 的漸增或漸減子數列。
  • (b) 證明任一至少 $ab+1$ 項的實數列, 必含一個 $a+1$ 個項的漸增子數列或一個 $b+1$ 項的漸減子數列。
• 33.
  • (a) 證明: 存在不全為零且絕對值小於一百萬的整數 $a$、 $b$、 $c$ 使 $$|a+b\sqrt{2}+c\sqrt{3}|\lt 10^{-11}.$$
  • (b) 若 $a$、 $b$、 $c$ 是不全為零且絕對值小於一百萬的整數, 求證: $$|a+b\sqrt{2}+c\sqrt{3}|\gt 10^{-21}.$$
  (美國, 41屆, A4)
• 34. 求證: 對任何正數 $\varepsilon\gt 0$, 存在正整數 $n$ 使 $$|\sin n-{1\over 2}|\lt \varepsilon.$$ (蘇聯, 1977)
• 35. 在邊長為1的正方形 $S$ 內任意取定五點 $P_1$, $P_2$, $P_3$, $P_4$, $P_5$, 用 $d_{ij}$ 表示點 $P_i$ 和 $P_j$ 的距離 $(1\le i \le j \le 5)$。 求證: 至少有一個 $d_{ij}$ 小於 ${\sqrt{2}\over 2}$。 用更小的數代替 $\sqrt{2}\over 2$, 命題還成立嗎? (美國, 14屆, A2)
• 36. 把邊長為1的正方形分成兩塊, 證明: 至少有一塊的直徑不小於 $\sqrt{5}\over 2$, 而且 $\sqrt{5}\over 2$ 是具有這種性質的最大數。 (這兒, 平面圖形的直徑指的是它上面任意兩點的距離的最大值。 比如, 邊長為1的正三角形的直徑是1, 等等。) (美國, 19屆, B3)

  

• 37. 求證: 在歐幾里得平面上, 不可能存在七條不同的直線, 使得至少存在六點, 每點恰為三條直線的交點; 至少存在四點, 每點恰為兩條直線的交點。 (美國, 34屆, A6)
• 38. 求證: 在任意的有限二項展延式中, 奇次項系數之和等於2的冪。 (美國, 16屆, A7)
• 39. $A_1,A_2,\ldots,A_{1066}$ 是有限集 $X$ 的子集, $|A_i|\gt {1\over 2} |X|$, $(i=1, 2,\ldots, 1066)$。 求證: $X$ 中存在10個元素 $x_1, x_2,\ldots, x_{10}$, 使得每個 $A_i$ 至少含 $x_1, x_2,\ldots, x_{10}$ 中的一個元素。 ($|S|$ 表示集合 $S$ 的元素個數。) (美國, 41屆, B4)
• 40. 一個正整數集合中, 如果不存在兩兩互質的三個數, 則稱它是 ``協力集''。 從1到16的整數集, ``協力集'' 最多可含多少個數? (美國, 35屆, A1)
• 41. 從 $1, 4, 7,\ldots, 97, 100$ 中選出20個數組成集合 $A$, 則 $A$ 中必有不同的兩組數, 其和都等於104。 (美國, 39屆, A1)
• 42. 給定 $mn+1$ 個正整數 $a_1,a_2,\ldots,a_{mn+1}$, $0\lt a_1\lt a_2\lt \cdots\lt a_{mn+1}$。 證明, 或者可以找到 $m+1$ 個數, 使它們中沒有一個數能夠被另一個數整除; 或者可以找到 $n+1$ 個數, 使得依大小排成序列, 除最前面的一個數外, 每個數都能被它前面的數整除。 (美國, 27屆, B4)
• 43. 空間中的六點, 任三點不共線, 成對地連接它們得十五條線段, 用紅色或藍色染這些線段 (一條線段只染一種顏色) , 求證: 無論如何染色, 恆存在同色的三角形。 (美國, 13屆, A2)
• 44. 在一個舞會上, 設沒有一個男孩同所有的女孩都跳過舞, 但是, 每個女孩至少同一個男孩跳過舞。 求證: 至少存在兩對舞伴: $g$、 $b$ 和 $g'$、 $b'$ ($b$、 $b'$ 是男孩, $g$、 $g'$ 是女孩) , 使得 $b$ 沒有同 $g'$ 跳過舞, 而 $g$ 和 $b'$ 也沒有跳過舞。 (美國, 26屆, A4)
• 45. 在三維歐幾里得空間中, 任意給定九個格點 (座標都是整數的點), 則其中必有兩點, 使得連接這兩點的線段內部含有格點。 (美國, 32屆, A1)
• 46. 任意給定 $n+1$ 個不超過 $2n$ 的正整數, 則至少有一個數是另一個數的倍數。 (美國, 19屆, B2)
• 47. 求證: 比 $(\sqrt{3}+1)^{2n}$ 大的最小整數能被 $2^{n+1}$ 整除。 (美國, 6屆, B5)
• 48. 在任意的十個連續整數中, 至少有一個與其餘九個數都互質。 (美國, 27屆, B2)
• 49. 大廳中聚會了100個客人, 他們中每個人都與其餘99人中的至少66人相識。 證明: 能夠出現這種情況: 這些客人中, 任何4人裡一定有兩人互不相識。 (我們假定, 所有的熟人都是彼此相識的, 亦即如果 $A$ 認識 $B$, 那麼 $B$ 也認識 $A$。)
• 50. 大廳中聚會了100個客人, 他們中每個都與其餘客人中至少67人相識。 證明: 在這些客人中一定可以找到4個客人, 他們中任何2人都彼此相識。 (和問題49一樣, 我們假定, 如果 $A$ 認識 $B$, 那麼 $B$ 認識 $A$。)
• 51. 所予 $4n$ 個正整數使得此 $4n$ 個整數中任取四個皆形成一比例。 證明此 $4n$ 個整數中至少有 $n$ 個為相同。
• 52. 任予四自然數 $A$, $B$, $C$, $D$, 依次取 $AB$, $BC$, $CD$, $DA$ 之差 (取正值) 記作 $A_1$, $B_1$, $C_1$, $D_1$, 再由 $A_1B_1$, $B_1C_1$, $C_1D_1$, $D_1A_1$ 之差 (取正值) 記作 $A_2$, $B_2$, $C_2$, $D_2$, 如此繼續, 證明: 取到最後必定可得四個零。 例如: 若所予四數為 32, 1, 110, 7 則可得下結果

  32,	1,	110,	7,
  31,	109,	103,	25,
  78,	6,	78,	6,
  72,	72,	72,	72,
  0,	0,	0,	0.

• 53.
  • (a) 試將1到100這一百個數重新排列, 使得找不到一組11個數 (無論相鄰或相隔) 以升或降的次序排列。
  • (b) 證明1到101這一百零一個數, 無論如何排列, 皆可找到一組11個數 (無論相鄰或相隔皆可) 以升或降的次序排列。
• 54.
  • (a) 1到200這二百個數中, 任意找出101個數, 證明此101個數中必定存在二數, 使得一數可被另一數整除。
  • (b) 1到200這二百個數中, 選出100個數, 使得其中沒有一個數可被其餘任何數整除。
  • (c) 1到200這二百個數中, 選出100個數, 若其中有一個數小於16, 證明100個數中, 必有一數可被另一數整除。
• 55.
  • (a) 證明任予52個正整數, 必存在二個數, 其差或和可被100整除。
  • (b) 證明任予100個皆不可被100整除的正整數, 一定可找到2個或2個以上的數之和可被100整除。
• 56. 一棋士準備以十一週的時間安排比賽, 每天至少比賽一場, 但為了免於過分疲勞, 規定每週不得超過十二場比賽, 證明必有連續若干天中, 此棋士恰比賽了二十場。
• 57. 設 $n$ 為一任意自然數。 證明存在一個 $n$ 的倍數, 而此倍數僅含有0與1。 再者, 如果 $n$ 與10互質 (即不能被2、5整除), 則存在某一 $n$ 的倍數完全是由1組成 (如果 $n$ 不是與10互質, 那麼當然不會有數目以 $11\cdots 1$ 的形式而能被 $n$ 整除)。
• 58. 已知數列 $$0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\ldots$$ 從第三數起每一數為前面二數之和 (此數列叫做 Fibonacci 數列)。 請問, 在這數列的前100,000,002項中, 是否存在一個末四位皆為零的數?
• 59. 是否存在一自然數 $n$, 使得 $(2+\sqrt{2})^n$ 的小數部分, 即 $(2+\sqrt{2})^n- [(2+\sqrt{2})^n]$ 大於0.999999?
• 60.
  • (a) 求證任何自然數 $n$, 整數 $[(2+\sqrt{3})^n]$ 為奇數。
  • (b) 找出能整除整數 $[(1+\sqrt{3})^n]$ 之2的最高乘冪。
• 61. 證明若 $p$ 為一奇質數, 則 $p$ 能整除 $[(2+\sqrt{5})^p]-2^{p+1}$。
• 62. 十七個人互相通信, 每一個人和其他人都互相寫信, 在他們信上的討論有三種不同的話題, 每一對筆友只寫一種話題。 證明至少有三個人他們筆談的是同一話題。
• 63. 證明從十個相異的二位數 (十進位制) 中, 可以選出兩個不相交的子集合, 使得其元素之數值和相等。
• 64. 考慮 $p$ 個方程式, $q=2p$ 個未知數 $x_1, x_2,\ldots, x_q$: \begin{eqnarray*} a_{11}x_1+a_{12}x_2+\cdots+a_{1q}x_q&=&0,\\ a_{21}x_1+a_{22}x_2+\cdots+a_{2q}x_q&=&0,\\ &\vdots&\\ a_{p1}x_1+a_{p2}x_2+\cdots+a_{pq}x_q&=&0, \end{eqnarray*} 係數 $a_{ij}\in \{-1, 0, 1\}$。 證明此組方程式有一解 $(x_1,x_2,\ldots,x_q)$ 使得
  • (a) 所有 $x_j$ $(j=1, 2,\ldots, q)$ 為整數。
  • (b) 至少有一個 $j$ 使 $x_j\not= 0$。
  • (c) $|x_j| \le q$ $(j=1, 2,\ldots, q)$。
• 65. 某一國際組織的1978名會員來自六個成員國, 會員分別編號為 $1, 2,\ldots, 1978$。 證明至少有一會員的標號, 恰為他同國家另兩位會員編號的和, 或為同國家另一位會員編號的兩倍。
• 66. 在平面上給了兩點 $O$、 $A$。 對平面上每一異於 $O$ 的點 $X$, 我們以 $\alpha(X)$ 表示介於 $OA$ 及 $OX$ 的角度的弧度數, 從 $OA$ 反時間方向度量。 $(0\le \alpha(X) \le 2\pi)$。 令 $C(X)$ 為以 $O$ 為圓心, 以長度 $OX+{\alpha(X)\over OX}$ 為半徑的圓。 平面上的每一點都塗上了有限多種顏色中的一種。 證明: 存在一點 $Y$ 使得 $\alpha(Y)\gt 0$, 而且其顏色出現在圓 $C(Y)$ 的圓周上。
• 67. 給了一個集合 $M$ 包含1985個相異正整數, 沒有一個的質因數超過26。 證明 $M$ 中至少包含一組4個相異元素其積為某整數的四次方。
• 68. 假設實數 $x_1, x_2,\ldots,x_n$ 滿足 $x_1^2+x_2^2+\cdots+x_n^2=1$。 求證: 對任意整數 $k\ge 2$, 存在 $n$ 個不全為零的整數 $a_i$, $|a_i|\le k-1$, $i=1, 2,\ldots, n$, 使得 $$|a_1x_1+a_2x_2+\cdots+a_nx_n| \le {(k-1)\sqrt{n}\over k^n-1}.$$

---本文作者任教於國立台灣大學數學系---