幸福结局问题-台大数学系.doc

從鴿籠原理到幸福結局問題 國立台灣大學數學系 張鎮華 .tw/~gjchang 2003年3月16日 摘要. 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)是多少？為了方便，我們用N0(n)表示這個最小正整數。很顯然的N0(3)＝3；而Klein的證明，再加上一個很簡單的例子（三角形的三個頂點及內部一點不構成凸四邊形），就可以得到N0(4)＝5。 在他們這一群人中，另一名數學家Endre Makai很快就證明了N0(5)＝9；也就是說，平面上任意三點不共線的任9點中，一定能找出5點構成凸五邊形，而且下面的例子顯示8點是不夠的： 由於知到N0(3)＝2＋1，N0(4)＝22＋1，N0(5)＝23＋1，他們動了N0(n)＝2n-2＋1的腦筋。過了一陣子他們就意識到，只靠簡單的論證並無濟於事，於是圈子裡引發出一股急於解決這個問題的激奮情緒。對Szekeres來說，解題的動機主要來自Klein，獲得佳人青睞強烈地激勵他爭取率先提出解法，幾個星期後他就面帶勝利的笑容對Erd?s說：『E.P.*，敞開你那充滿智慧的大腦吧！』Szekeres找出了保證可構成凸n邊形的所需點數，但這個數目比他們猜想的2n-2＋1大很多； ___________________________________________________________________________ * E.P.係Erd?s Paul的縮寫，和中國人一樣，匈牙利人的姓是寫在前面的。 儘管如此，他的證明還是贏得了Klein的芳心，四年後有情人終成眷屬。從此Erd?s把這個問題稱為「幸福結局問題」，永垂數學史。 Szekeres的證明隱含了拉姆西定理，事實上，拉姆西定理大約在這五年之前提出來，Szekeres可以說是在不知情的狀況下獨立重新發展出拉姆西定理。用後面將介