从鸽笼原理到幸福结局问题

《从鸽笼原理到幸福结局问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、从鸽笼原理到幸福结局问题從鴿籠原理到幸福結局問題國立台灣大學數學系張鎮華http://www.math.ntu.edu.tw/~gjchang2003年3月16日摘要.1932年Klein提出這樣的問題：對於給定的正整數n，能否找到一個正整數N(n)，使得平面上任意N(n)點（其中任三點不共線）中，均能找到n點形成凸多邊形。這篇文章主要是在介紹這個被Erd?s稱為「幸福結局問題」的來龍去脈，並討論鴿籠原理與拉姆西理論，及他們如何應用在這個問題上。一、人物出場　　匈牙利數學奇才PaulErd?s於1996年9月24日以八十三歲高齡去世，他一生寫過的學術論文達14

2、75篇，不只數目多，而且分量紮實，其中有許多影響後來的發展甚深。現在要談的是他年輕時和Szekeres合力解決Klein提出來的一個平面幾何問題的一段歷史，以及其後的影響。　　Erd?s於1913年3月26日出生在匈牙利，自小就已顯露其數學才能。1930年代初，Erd?s和一些年輕數學家們每週聚會一次，一起聊天、談論時事，尤其是研討數學。週日他們去布達佩斯郊外爬山越嶺，也常在城市公園裡披斗篷的無名者青銅像下的長椅上聚會。　　在無名者銅像下，Erd?s和他的夥伴們有關政治和家庭的話題，總是不如數學多。他們沉迷於數學，其中尤以Erd?s最為癡迷，他的熱衷數學，很能

3、帶動同伴們的討論。　　1932年歲末，在無名者銅像下聚會的人群中多了EstherKlein，她是一個在哥廷根大學唸了一學期，中途跑出來，頗有才華的學生，還有GyorgySzekeres，他是一個急於把試管拋掉而投身數學的化學系畢業生。　　有一次，在他們每週的活動中，Klein提出一個希奇古怪的平面幾何問題：平面上給定五點，若任意三點不共線，求證必有四點構成凸四邊形。（一個四邊形是由四條只交在端點的邊構成的圖形，正方形、矩形、平行四邊形和梯形都是四邊形；同理可以有五邊形、n邊形等多邊形。至於「凸」是指從多邊形內部任意一點都可以直接「看到」另外一點，也就是，凸多邊

4、形內部任意兩點的連線仍在該多邊形內部；所以正方形是凸四邊形，而成箭頭狀的四邊形不是凸四邊形，因為位於一側箭尾的點不能直接「看到」位於另一側箭尾的點。）　　　　　　Klein證明平面上任意三點都不共線的五點，不外乎下面三種情況，而每種情況下都保證能構成一個凸四邊形，定理從而得證。　　第一種情況是五點自身就構成一個凸五邊形，其中任意四點均構成凸四邊形。　　第二種情況是其中一點為其餘四點所包圍，則外部四點構成凸四邊形。　　　　　　第三種情況是其中兩點位於其餘三點所構成的三角形內部。若作一直線通過這兩點，則該直二、幸福結局問題　　大家都很喜歡Klein這個簡練的證明，

5、於是想要將證明推廣到構成更多邊的凸多邊形。更精確的來說，Klein建議一個這樣的問題：　　對於給定的正整數n，能否找到一個正整數N(n)，使得平面上任意N(n)點（其中任三點不共線）中，均能找到n點形成凸多邊形？　　　　這個問題包括兩件事情，首先，這樣的N(n)是否一定存在？其次，如果存在，那麼最小的N(n)是多少？為了方便，我們用N0(n)表示這個最小正整數。很顯然的N0(3)＝3；而Klein的證明，再加上一個很簡單的例子（三角形的三個頂點及內部一點不構成凸四邊形），就可以得到N0(4)＝5。　　在他們這一群人中，另一名數學家EndreMakai很快就證明

6、了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邊

7、形的所需點數，但這個數目比他們猜想的2n-2＋1大很多；___________________________________________________________________________*E.P.係Erd?sPaul的縮寫，和中國人一樣，匈牙利人的姓是寫在前面的。儘管如此，他的證明還是贏得了Klein的芳心，四年後有情人終成眷屬。從此Erd?s把這個問題稱為「幸福結局問題」，永垂數學史。　　Szekeres的證明隱含了拉姆西定理，事實上，拉姆西定理大約在這五年之前提出來，Szekeres可以說是在不知情的狀況下獨立重新發展出拉姆西定理。用後

8、面將介紹的符號表示，他得到　　N0(n