幸福结局问题一一.PDF

幸福結局問題 一一 鴿籠原理與拉姆西定理 張鎮華 摘要. 1932年 Klein 提出這樣的問題: 對於給定的正整數 n, 能否找到一個正 整數 N (n), 使得平面上任意 N (n) 點 (其中任三點不共線) 中, 均能找到 n 點形 成凸多邊形。 本文首先介紹這個被 Erd¨os 稱為 「幸福結局問題」 的來龍去脈, 並討 論鴿籠原理與拉姆西定理 , 及他們如何應用在這個問題上。 一. 人物出場 匈牙利數學奇才 Paul Erd˝os 於 1996年 9 月24 日以八十三歲高齡去世, 他一生寫過的學 術論文達 1475篇, 不只數目多, 而且分量紮實, 其中有許多影響後來的發展甚深。 現在要談的 是他年輕時和 Szekeres 合力解決 Klein 提出來的一個平面幾何問題的一段歷史, 以及其後的 影響。 Erd˝os 於 1913年 3 月26 日出生在匈牙利, 自小就已顯露其數學才能。 1930年代初, Erd˝os 和一些年輕數學家們每週聚會一次, 一起聊天、 談論時事 , 尤其是研討數學。 週 日他們去布達佩 斯郊外爬山越嶺, 也常在城市公園裡披斗篷的無名者青銅像下的長椅上聚會。 在無名者銅像下, Erd˝os 和他的夥伴們有關政治和家庭的話題, 總是不如數學多。 他們沉 迷於數學, 其中尤以 Erd˝os 最為癡迷, 他的熱衷數學, 很能帶動同伴們的討論。 1932年歲末, 在無名者銅像下聚會的人群中多了 Esther Klein, 她是一個在哥廷根大學 唸了一學期, 中途跑出來, 頗有才華的學生, 還有 Gyorgy Szekeres, 他是一個急於把試管拋掉 而投身數學的化學系畢業生。 有一次, 在他們每週的活動中, Klein 提出一個希奇古怪的平面幾何問題: 平面上給定五 點, 若任意三點不共線, 求證必有四點構成凸四邊形。 (一個四邊形是由四條只交在端點的邊構 成的圖形, 正方形、 矩形、 平行四邊形和梯形都是四邊形; 同理可以有五邊形、 n 邊形等多邊形。 28 幸福結局問題 — 鴿籠原理與拉姆西定理 29 至於 「凸」 是指從多邊形內部任意一點都可以直接 「看到」 另外一點, 也就是, 凸多邊形內部任 意兩點的連線仍在該多邊形內部; 所以正方形是凸四邊形, 而成箭頭狀的四邊形不是凸四邊形, 因為位於一側箭尾的點不能直接 「看到」 位於另一側箭尾的點。) Klein 證明平面上任意三點都不共線的五點, 不外乎下面三種情況, 而每種情況下都保證 能構成一個凸四邊形, 定理從而得證。 第一種情況是五點自身就構成一個凸五邊形, 其中任意四點均構成凸四邊形。 第二種情況是其中一點為其餘四點所包圍, 則外部四點構成凸四邊形。 第三種情況是其中兩點位於其餘三點所構成的三角形內部。 若作一直線通過這兩點, 則該 直線將三角形分為兩部分, 必有兩個頂點位於直線的一端, 那麼這兩頂點與原來的兩點構成凸 四邊形。 30 數學傳播 28 卷 2 期 民 93 年 6 月 二. 幸福結局問題 大家都很喜歡 Klein 這個簡練的證明, 於是想要將證明推廣到構成更多邊的凸多邊形。 更 精確的來說, Klein 建議一個這樣的問題: 對於給定的正整數 n, 能否找到一個正整數 N (n), 使得平面上任意 N (n) 點 (其中任三點不共線) 中, 均能找到 n 點形成凸多邊形? 這個問題包括兩件事情, 首先, 這樣的 N (n) 是否一定存在? 其次, 如果存在, 那麼最小 的 N (n) 是多少? 為了方便, 我們用 N (n) 表示這個最小正整數。 很顯然的 N (3) = 3; 而 0 0 Klein 的證明, 再加上一個很簡單的例子 (三角形的三個頂點及內部一點不構成凸四邊形), 就 可以得到 N (4) = 5。 0