張貼日期:Jun 30, 2015 6:19:19 AM
作者:陳宏賓 副教授(國立中興大學應用數學系)
圖片取自 www.Pinterest.com
愛一個人需要理由嗎?你若曾經深深愛上一個人,那種心情現在還記得嗎,如果有,愛上他/她的理由是甚麼呢? 是至尊寶與紫青寶劍的命中注定,還是豬八戒陰錯陽差的一個冷顫,或者媲美來福的文采,又甚至是綺夢腋下的一顆痣。愛一個人,真的需要理由嗎? 今天的故事要開始囉.....
時間回到 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, ...一個一個討論下去簡直沒完沒了,最根本的第一層問題沒解決,是破不了關的。
圖片取自 葉問2 劇照
於是,存在性就像個破壞力十足又耐打的世界拳王,囂張的擋在眾人面前。一時之間,看起來毫無破綻。
「不可能的! 不可能毫無破綻! 為了 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=22 +1
ES(5)=9=23 +1
Klein:「這似乎可以推導出一個公式。」
Szekeres 的OS: <比起推導公式,我更想要推倒妳阿!!>
Klein:「下流!」
Szekeres:「心聲妳也聽得到 ?」
後來,Erdős 和 Szekeres (1935) 將一系列的討論和發現,寫成一份論文,內容就包括下面這個數學猜想
ES(n)= 2n-2 +1
只是,這個大魔王的血條超長,至今還沒有任何數學家或團隊能夠戰勝它。
目前只知道 n=6 還是對的,Szekeres 和 Peters 在 2006 年的一篇論文裡用電腦輔助證明了 ES(6)=17 (論文刊出時 Szekeres 已經過世),而 n大於6 以上至今都還是未知。
上下界
Erdős 和 Szekeres (1935) 提出了一般的上下界
之後上界陸續有些許改進,包括
Kleitman and Pachter (1998)
目前最好的是
不要小看這些微小的進展,隨著 n 變大,這些值的差也越來越大,不信你可以試試 n=6 的情況。
R( n, 5; 4) 存在嗎?
這個牽涉到拉姆西理論的問題,容我賣個關子,日後分曉囉。
參考資料:
Computer solution to the 17-point Erdős-Szekeres problem, Szekeres and Peters