張貼日期：Jun 30, 2015 6:19:19 AM

愛一個人需要理由嗎?你若曾經深深愛上一個人，那種心情現在還記得嗎，如果有，愛上他/她的理由是甚麼呢? 是至尊寶與紫青寶劍的命中注定，還是豬八戒陰錯陽差的一個冷顫，或者媲美來福的文采，又甚至是綺夢腋下的一顆痣。愛一個人，真的需要理由嗎? 今天的故事要開始囉.....

時間回到 1930 年代的一個遙遠的美麗國度 － 布達佩斯.匈牙利。

某天，下了小雨的午後空氣還有點潮濕，街道上的小販正忙進忙出將淋了雨的攤位整理一翻，幾條街道匯聚在中央公園廣場，廣場上立著一座無名的青銅像，前方草地上的長椅附近，圍繞了幾個年輕人，在這之中有一位年輕貌美的女子， 神情顯得有點不耐。

Szekeres:「Esther ~ Esther ~ 明天下午有沒有空，我最近剛學了一樣魔術，明天可以約在妳家表演給妳看。」

Erdős: 「可不可以順便吃蛋塔和喝奶茶，我還有點餓。」

Klein:「......我以為，只有年輕人，沒有經驗，才會用這種老套的辦法來追女孩子呢。

沒想到像你這麼成熟的男人，也會用這種老招來追女孩子啊。」

Erdős: 「不是阿！我並不...」

Szekeres: 「你成熟?」

Erdős : 「我成熟! (挺胸)」

Klein:「我一向啊就覺得，男人要留鬍子、要有點肚子，超過四十歲，才有男人味兒。

不像那些個年輕小鬼，穿著五顏六色的 T 恤，戴隻卡通錶，一點男人味也沒有。」

Erdős : 「說得對，說得對。」

Klein:「唉～ （嘆氣）最近有一個關於平面幾何的問題，一直想不出來，煩都煩死了。」

Szekeres: 「妳數學解不出來可以跟我說啊!」

Klein: 「可是...這題是 S 級的呀。」

Szekeres: 「這個....妳可以跟 Paul 說啊!」

(平時有在follow UniMath的讀者，一定都知道鼎鼎大名的 Paul Erdős 吧!)

Erdős: 「Esther~ 妳就先說說看嘛。」

Klein: 「好吧! 是這樣子的。在平面上隨便丟 5 個點，任 3 點不可以落在同一條直線上，

那麼一定會有某 4 個點會形成凸四邊形。」

(註: 四邊形就是由四條只交在端點的邊構成的圖形，正方形、長方形、平行四邊形都是四邊形。至於「凸」是指任意一個端點都可以直接從四邊形內部「看到」另外一點，不會被邊擋住。也就是，凸多邊形內部任意兩點的連線仍在該多邊形內部; 所以正方形是凸四邊形, 而成箭頭狀的四邊形不是凸四邊形, 因為位於一側箭尾的點不能直接「看到」位於另一側箭尾的點。)

Szekeres: 「有這種事!

有這種事!

有這種事! 」

Klein 得意地笑著說: 「這個我可以證明。

其實平面上任意 3 點不共線的 5 個點，就只有下面這三種情況:

外包是五邊形、四邊形以及三角形。前兩種理所當然會有凸四邊形，

三角形內部兩點與三角形的其中兩點也會構成凸四邊形。

無論哪一種，都有凸四邊形。」

Klein: 「令我困擾的是，如果是五邊形、六邊形、七邊形，要多少個點才能保證存在呢？

甚至更一般的問題: 針對任意的 凸的 n 多邊形，能不能找到一個正整數 N(n)，

使得平面上任意灑 N(n) 點 (其中任意三點都不共線) , 都會保證其存在呢?」

頓時，眾人沉默了下來，所有聲音彷彿被吸進了黑洞，大家動也不動，只有腦袋正快速的運轉著，思考著如何破解這記強有力的正中直拳。

在高手的眼中，Klein 這個問題，有兩個層面要突破:

第一層是，這樣的正整數 N(n) 是否一定存在? 這是最根本的問題，如果沒有這樣的一個數，那就結束了。

第二層是，如果存在的話，最小的那個數又是多少呢?

(為了紀念 Erdős 和 Szekeres，後來用 ES(n) 來表示這個最小的數)

顯而易見，平面上任意丟 3 個點都會形成凸三角形，所以 ES(3)=3；而 Klein 的證明加上簡單的補充，說明只有 4 個點的話，的確有可能無法形成凸四邊形，因此可以得到 ES(4)=5。只是，你知道，我知道，獨眼龍也知道，這樣 n=3, 4, ...一個一個討論下去簡直沒完沒了，最根本的第一層問題沒解決，是破不了關的。

於是，存在性就像個破壞力十足又耐打的世界拳王，囂張的擋在眾人面前。一時之間，看起來毫無破綻。

「不可能的! 不可能毫無破綻! 為了 Klein 的幸福，我一定要打敗它啊啊啊!」Szekeres 心想。

日以繼夜，夜以繼日，Szekeres 不停努力戰鬥著，不斷地思考如何破解拳王的套路。也不知道過了多久，忽然有一股聲音在耳朵旁，越來越清晰。

謎之聲: 「Szekeres~ 何不試試攻他中路。」

就這樣，擁有比其他人更強烈的動機，Szekeres 將愛情化為力量，灌注在右手，一個箭步，揮出致勝的一擊。

Szekeres 終於找到了平面上保證可以有凸 n 邊形所需要的點數。

拳王，敗!

拉姆西理論

Szekeres 的證明隱含了拉姆西理論 (Ramsey Theory)，用拉姆西理論的語言來說，Szekeres 找到的這個數可以表成 R(n,5;4)，雖然我們不知道這個確切數字是多少。

請先想像 R(n,5;4)是一個明確的數字，意思是將任意 R(n,5;4) 個點，將其任意 4 個點所形成的子集合們，再任意分成兩類，第一類是 4 點會構成一個凸四邊形的子集，第二類是 4 點不構成凸四邊形的子集。這麼做之後會發生:

要嘛 (1) 會有 n 個點，其任意 4 個點都會形成凸四邊形；

不然就是 (2) 會有 5 個點，其任意 4 個點都不會形成凸四邊形。

而 Klein 的證明已經知道 (2) 是不可能發生的，因此 (1) 就必定成立了。而這個時候，這 n 個點也必定會形成凸 n 邊形，得證。

Szekeres 的證明成功打敗了第一層的魔王，也贏得了 Klein 的芳心，四年之後，有情人終成眷屬。就像童話故事一樣，王子和公主從此過著幸福快樂的日子。因此緣故，Erdős 把這個問題稱為「幸福結局問題 Happy End Problem」。在兵器譜數學史羅曼蒂克排行榜上，排名第三，至於第二和第一，等我日後想起來再說吧，絕對不是小李飛刀他娘(誤)!

一轉眼，經過了數十寒暑，一代數學宗師 Erdős 於 1996 年過世，享壽 83 歲，而這對數學界才子佳人，也在 2005 年辭世，Szekeres 享壽 94，Klein 享壽 95。令人稱奇的是，兩人早就約好似的，離開人世的時間僅僅只相隔一個小時。結髮超過一甲子，雖不能同年同月同日生，能夠同年同月同日死，對一對戀人來說也算是一種幸福結局了。

後記

第二層大魔王呢?

眾人之中有個名叫 Endre Makai 的傢伙，在 Klein 提出問題不久後，很快就發現 ES(5)=9。綜合之前的結果，

ES(3)=3=2+1

ES(4)=5=2² +1

ES(5)=9=2³ +1

Klein:「這似乎可以推導出一個公式。」

Szekeres 的OS: <比起推導公式，我更想要推倒妳阿!!>

Klein:「下流!」

Szekeres:「心聲妳也聽得到 ?」

後來，Erdős 和 Szekeres (1935) 將一系列的討論和發現，寫成一份論文，內容就包括下面這個數學猜想

ES(n)= 2^n-2 +1

只是，這個大魔王的血條超長，至今還沒有任何數學家或團隊能夠戰勝它。

目前只知道 n=6 還是對的，Szekeres 和 Peters 在 2006 年的一篇論文裡用電腦輔助證明了 ES(6)=17 (論文刊出時 Szekeres 已經過世)，而 n大於6 以上至今都還是未知。

上下界

Erdős 和 Szekeres (1935) 提出了一般的上下界

之後上界陸續有些許改進，包括

目前最好的是

不要小看這些微小的進展，隨著 n 變大，這些值的差也越來越大，不信你可以試試 n=6 的情況。

R( n, 5; 4) 存在嗎?

這個牽涉到拉姆西理論的問題，容我賣個關子，日後分曉囉。

參考資料:

幸福結局問題一一鴿籠原理與拉姆西定理, 張鎮華 (台大數學系教授)

A world ofteaching and numbers - times two, Michael Cowling

Computer solution to the 17-point Erdős-Szekeres problem, Szekeres and Peters