Embedded Files
張貼日期：Sep 23, 2020 4:52:55 PM
背景圖片取自 pxhere.com
日前我們報告了喜訊，2020 年國際數學奧林匹亞（IMO），台灣隊的題目首次登上壓軸第六題。正式考試的題目敘述如下：
第六題 證明存在一個正數 c 使得以下敘述成立：考慮正整數 n>1，以及一個由在平面上 n 個點所形成的集合 S，滿足 S 中任意兩點的距離至少是 1。 則存在一條隔離 S 的直線 L 使得每一個 S 中的點與 L 的距離至少是 cn-1/3。
（稱 L 為一條隔離Ｓ的直線若某些由Ｓ中兩個點連成的線段穿過 L。）
註：如果 cn-1/3 換成了較弱的結果 cn-α，會根據常數 α>1/3 之值給予分數。
圖像上來解釋的話就是說，如果有 n 個點，只要這些點兩兩之間的距離都至少是 1，你就必然可以找到一條切過這些點的直線Ｌ，使得Ｌ跟最近的點的距離不小於 cn-1/3。如下圖，你把點想成藍莓也可以，如果肚子餓的話。
換言之，這題要你證明一定存在某種把這群點隔離成兩群的方式。隔離這兩個字很重要，因為這是個始於隔離，終於隔離的故事。
※ ※ ※
隔離竟然成了設計題目的靈感
故事要從我們的主人翁一號，前國手余竑勳（2013 銀牌、2014 金牌）開始說起。余竑勳目前就讀美國麻省理工學院資訊工程學系，但大家也知道，美國現在 COVID-19 疫情一發不可收拾，學校各種封校，很多留學生都避難回台灣，包括余前國手。
所以他就回來了。
然後他就被隔離了，居家隔離 14 天。據他本人表示：
以上轉自余竑勳在 AoPS 上的回憶錄
簡單翻譯一下，就是余竑勳被關到太無聊了，於是他就私訊敲了我們的主人翁二號，前國手林庭風（2018 銀牌）。林庭風表示「那你給一個動詞，我們來編題」。
猜猜余竑勳回了什麼動詞？
防雷分隔線
以上轉自林庭風在臉書上的回憶錄
然後事情就一發不可收拾了。剛好在修機器學習[1]（Machine Learning）的林庭風變出了這個題目的雛型，然後兩人共同把解答生出來，最後成功的變成台灣隊史上第一個登上 IMO 第六題的題目。(史上第一次入選是 1999 年第四題，由台師大數學系朱亮儒教授設計)
這件事得來不易。一來，IMO 的第三題與第六題是每一天的壓軸，通常都要是最難的，但卻又要可以用中學的初等作法做得出來，出題難度很高。再者，就算設計出來，還得和全世界各國投的題目一起競爭，就算題目設計很漂亮，也難保真的會被選上。
在此恭喜兩位前國手達成人生成就。
※ ※ ※
原始版本
整個題目從開始編到最後的版本，中間的過程也是命運多舛。這是此題的原始版本：
平面上有 n 個點，各代表一個人。基於疫情關係，這些人被要求保持社交距離，人與人之間的距離至少必須為 1。為了進一步防止疫情擴散，政府決定興建一座隔離牆，也就是牆的兩側都要有人，而且人離牆的距離越遠越好。
用數學語言來說，牆是平面上的一條直線，將人分為兩個非空的子集。令 d 為距離牆最近的人到牆的距離；政府希望能夠極大化 d 值，以最大程度隔開兩群人。
直覺上來看，人的密度越高，則人和牆的距離勢必就會越小。這道題要問的就是找出這個關係。
試證明存在常數 c，使得不管 n 是多大，人如何散佈，政府都可以蓋出一座牆使得 d ≧ cn-1/2。
對，這是個充滿疫情的題目．．．
原始版本的解法其實沒有太難。我們就先想一下，撇開這些數字問題，如果我純粹是有一塊大蛋糕，上面灑了一大堆藍莓，然後我要你找一個「最不容易切到藍莓」的地方切下去，你會怎麼切？
你勢必是去找「藍莓最稀疏」的那個地方吧？把蛋糕想成平面，藍莓想成人，你就知道了。
數學思維其實就是系統性的去證明，這個最稀疏的地方存在，而且足夠稀疏。
有個簡單的想法是這樣子：在這些人裡面找到距離最遠的兩人，想像這兩人所在的那個扁平世界，其他人就像一端繫在地上飄浮空中的氣球，那些線垂直於扁平世界（無風的狀態），此時我們想切的那一刀，就選在線頭彼此離最遠的中點。
剩下的問題是，這樣做能保證多少距離呢？
首先，可以估計出最遠的兩人距離至少 kn1/2 （k為常數），接著套用鴿籠原理可知 n 個線頭中一定有兩個相鄰線頭距離至少是全長的 1/(n-1) ，你從中間切一刀的話，至少就隔開了 (k/2) n-1/2，即為所求。
證明細節如下：
1. 首先我們看看整群人到底會散多開。令直徑 D 為距離最遠的兩個人的距離。
性質一：存在常數 k 使得不管 n 是多少，都有 D ≧ kn1/2。
證明：易知這 n 個人都會在一個邊長為 D 的大正方形裡面。考慮以每一人為圓心，半徑 1/2 作圓，則這 n 個圓都會在一個邊長為 D+1/2 的正方形裡面。由於每個人之間的距離都至少是 1，因此這些圓兩兩不相交（頂多相切）。這表示所有圓的面積和一定小於正方形的面積和，也就是 ，化簡一下就得到性質一。
2. 接下來我們要利用這個直徑，也就是相對「散得很開」的方向，來找剛剛那個所謂「較稀疏」的地方。利用鴿籠原理，我們可以得到這個：
性質二：存在一條直線，使得 d ≧ D/2n。
證明：令 P 和 Q 是相距最遠的兩個人（也就是直徑 D 的兩端）。考慮所有人對 PQ 線段的投影點。這會得到 n個投影點，把 PQ 線段分成 n-1 個子線段，從而由鴿籠原理知必有一個子線段的長度不小於 D/(n-1)。不難知道，選這個子線段的中垂線即為所求。
結合性質一與二，我們便有一條直線，使得 d ≧ D/2n ≧ kn1/2/2n = (k/2) n-1/2，從而證完原題。
※ ※ ※
ＩＭＯ選中更難的版本
不過眼尖的讀者可能發現哪裡怪怪的了。咦~ 為什麼是 n-1/2 啊？IMO 的第六題不是要求 n-1/3 嗎？這個故事就有趣了．．．
話說當時兩位前國手編好 n-1/2 的版本時，都仍相信 n-1/2 就是最緊的答案，直到他們決定要把題目投給 IMO，開始打解答與說明文件，想說應該要附上一個 n-1/2 是最緊的例子那一刻．．．
．．．卻發現 n-1/2 不是最緊的．．．n-1/3 才是．．．
根據林庭風前國手的回憶錄，「據余說發現 -1/2 是錯的到做完 -1/3 並證明是 optimal (估計+構造) 花了十幾個小時，然後我估計的部份大概花了四個多小時 ( IMO 考的部份)」。換言之，這個 n-1/3 的解題難度，遠遠大於 n-1/2的難度，有興趣的朋友可以參考這個相對漂亮的解法。
事實上，n-1/3 相對難很多，以至於他們投題的時候還是投 n-1/2 的版本，但是在附註中詳述了 n-1/3 版本。原本以為大會頂多會拿 n-1/2 版本當成第四題，但當題目翻譯組看到大會居然選了這一題，而且居然是直接拿 n-1/3 版本當成第六題時，一方面是為台灣隊登上第六題感到興奮不已，另一方面則心想「糟了! 這會不會太難啊？」
至於是不是真的太難，全球到底會有幾個人做出來，就請靜候這幾天 IMO 成績協調的結果！
[1] 事實上這個隔離直線與機器學習中Supporting Vector Machine（SVM）有相當程度的關係。
作者簡介
高竹嵐－現職交通大學統計所助理教授，台灣合唱、阿卡貝拉與音樂劇作曲家、桌遊測試師與設計師、桌遊代理商新天鵝堡特約翻譯。參與作品有厄夜魔堡、調香師、數感傳奇、時光當鋪、醫藥先鋒...等。
Page updated
Report abuse