[其他] Erd"os 的偏移問題

看板Math作者Giawgwan (教官)時間7年前 (2016/11/21 22:21)推噓27(27推 0噓 7→)

留言34則, 29人參與討論串1/1

最近10年，「匈牙利風格」的組合數學有非常豐碩的進展。匈牙利風格組合數學的關鍵人物之一，是一生行事都非常戲劇化的艾狄胥(Erd"os P'al)。 1996年過世的艾狄胥，原創性與對整數的敏感異於常人，他提出了非常多的猜想，其中還是有許多至今懸疑數十年沒有進展。但前年有個非常有名的艾狄胥問題被解決了: 就是底下要介紹的「艾狄胥的偏移問題（The Erd"os Discrepancy Problem）」 ********************** 假設你被綁架，困在原點。往右 2 步就是懸崖，往左 2 步也是懸崖。綁匪告訴你可以起來走 11 步「動動筋骨」，但是要把你每一步想走的向左或向右的順序先告訴他。然後，他會逼迫你按照你寫的順序走（可憐的你也只好照做，人在槍口下，不得不低頭）。所以啦，為了不掉下懸崖，你當然不要一次走兩個右或兩個左。把向右記為 O，向左記為 X，你給的順序也許是：OXOXOXOXOX，這樣就在0與1之間擺盪，不會掉下懸崖。 ******************* 然而這個綁匪喜歡數學。(奇妙的設定) 雖然你給了他一個往左往右的 OX 字串，他卻不一定要一個一個讀這個字串。他也可能兩個兩個讀（只讀第 2、4、6…個符號），或三個三個讀，或四個四個讀…。也就是說，他看著你給的字串，不一定要你走第 1、2、3、4、5、6、7、8、9、10、11步，也許會逼你按第 2、4、6、8、10 步的走法來走，也可能逼你走第 3、6、9 步，或逼你走第 4、8 步，或逼你走第 5、10步。綁匪也很有義氣地承諾，如果你能夠給一個字串，不論他怎麼讀，你都不會掉下懸崖，就當場釋放你。這樣，剛剛那個 OXOXOXOXOX 就不能用了 ---- 綁匪取 2、4，你就連走兩步往左掉下懸崖了。 ******************** 所以怎麼辦呢？第一步如果往右（O），第二步一定要往左（OX）。第三步呢？第三步一定要往左！因為如果第三步往右（OXO），第四步勢必要往左（OXOX）。但此時邪惡的綁匪如果逼你走 2、4步就完了。所以第三步要往左（OXX）。接著，第四步不能往左，否則取 2、4 步一樣掉下懸崖。因此前四步是OXXO。 ******************** 聰明的你也許到這裡會說「那就重複以上OXXO 的模式就好了」。很抱歉，錯。按照這樣的模式，前八步是 OXXOOXXO ---- 的確，一步一步走或是取 2、4、6、8，都不會掉下懸崖 ---- 但是綁匪如果三個三個數，要你走 3、6，那就完了。我建議網友現在可以先停下來，思考一下這個非常有趣的謎題。你能設計出一個長為 11 的OX字串，讓自己安然脫困嗎？先公布答案，答案是「可以」(安全脫困的字串放在本文最後) ********************* 但是，如果一開始綁匪要求你走 12 步，那數學告訴我們，放棄求生算了，因為，你不可能設計出一個長為 12 的安全字串。也就是說， "不管" 這個字串長得怎樣（共有 2^12 = 4096 種可能），綁匪 "一定能" 找到一個讀法，讓你掉下懸崖! ********************** 以上就是艾狄胥偏移問題的簡單情形。接下來我們把問題數學化。如果懸崖兩邊寬一點，比如說在 ±3掉下懸崖。則 12 步是有安全字串的，事實上，甚至走 100 步也有安全字串，網友能設計出來嗎？這裡給網友一個極困難的挑戰 : 此時最長的安全字串有多長？ (繼續讀下去就知道這個看起來不怎麼樣的問題實際上有多困難。) ********************** 換個角度想，如果懸崖的兩邊都非常遠，那直覺上，安全字串就可以非常長了。那，是不是有一個無限長度的安全字串呢？比如說，懸崖兩邊都距離原點 100 萬步。那有沒有一個無限長度的字串，讀 1、2、3… ；或 2、4、6…；或 3、6、9…；或 4、8、12…等，都不會掉到懸崖下？艾狄胥猜「沒有這種無限字串」。1932 年，他猜測，不管懸崖兩邊有多遠，則任意一個無限長度的字串，一定可以找到一個讀法讓你掉下懸崖。就是說，任何一個無限長度的字串，「偏移」的程度都可以無限大。 *********************** 這就是所謂的艾狄胥偏移問題。數學符號的說法是：給定一個正整數 C（懸崖兩邊距離原點的距離為 C + 1）。則對於任何一個由 1,-1 所形成的無限字串：x1, x2, x3, x4,…, 一定可以找到 d（幾個幾個讀）和 n（讀到多長），使得 | x_d + x_(2d) + x_(3d) +.... + x_(nd) | > C （這裡 > C就是表示掉到懸崖下了） ************************ 2010 年，由數學家陶哲軒所發起的網路共同研究的多工數學（polymath）計畫選上了這個問題，得到了一些部分結果。如上面討論的，懸崖在 ±2時，只要字串長度大於等於 12 就會掉下懸崖。而懸崖在 ±3 時已經非常困難：2014年，數學家李西札（Alexei Lisitsa）和科涅夫（Boris Konev）說，當懸崖在 ±3時，任何一個長度大於或等於 1161 的字串，都會掉下懸崖。他們試著設計電腦演算法來證明這個結果，用掉了電腦 13 G 的容量 --- 比當時整個維基百科（Wikipedia）的內容還多！為什麼這麼難？關鍵是 1161 這個數字。首先，要檢驗對於任意一個長為 1161 的字串，都有一種讀法讓它偏移會跑到 3 或 -3. 光是這樣的字串就有 2^(1161) 個！每一個還要檢驗它的確會掉到懸崖下。其次，還要設計出一個長度是 1160 的安全字串, 讓它不管怎麼讀偏移都不會跑到 ±3。 ************************** 這還是僅僅在懸崖在±3，也就是 C = 2 的狀況而已！所以，當陶哲軒在 2015 年宣稱 "完全解決" 了艾狄胥偏移猜想，在數學界是一個轟動一時的新聞。他的方法結合了 2010 年多工數學計畫得到的部分結果，與數論上積性函數來衡量數列的混亂性。總之，他證明了艾狄胥偏移猜想成立。也就是說, 不管 C 是多少，任何一個無限字串一定會掉到懸崖下。高懸 80 年的猜想因此解決。陶哲軒在證明方法中引進的許多想法是原創的，咸信能夠用在更多的問題上。 *************************** 最後我們公布懸崖在 ±2 時的 11 步安全字串的解答： OXXOXOOXXOO （這是其中一組解，還有其他的可能）。 *************************** 追根究底的讀者也許會問，那當懸崖在 ±3時，不是說有一個長為 1160 的安全字串嗎？那字串長得什麼樣子？真的想知道嗎? 長這樣。 OXXOXOOXXOXXOXOOXOOXXOXOOXOOXXOXOOXXOXXOXOXXOOXXOXOOOXOXXO XOOXOOXXXXOOXOOXXOXOOXXOXXOOOOXXOXXOXOXXOOXXOXOXOOOXXOXOOX XOXXOXOOXXOXOOXOOOXOXXOXOOXXOXXOXOOXOOXXOXXOXOOXXOXOOXXXOX OXOOOOXXXOXOOXOOXXXOOOXXOXXOXOOXOOXXXOOXOXOXOOXOXXXOXXOXOO XOOXXOXOOXXOXXOXOOXOOXXOOXXXOOOXXXOXOOOXXOXOOXXOOXOXOOXOXX XOXOOXXOXXOXOOXXOXOOXOOXXOXOOXXOOXOXXOXOXOOXOXOXXOXOOXXOXO OXOOXXOXOXOXXOXOXOXXOOOXOXOOXXXXOOXOOOXXOXOXXOXOOXXOXOOXOO XXOXOOXXXXOOXOOOXOXXXXOOXOOXXOXXOXOOXXOXOOXOOXXOXOOXXOXXOX OOXXOXOOXOOXXOXXOXOOOOXXXOXOOXXOOXXXOOOXOXXOXOOXOXXOOOXOXX OXXOXOOXOOXXOOXXXXOXOOXOOXOOXXXXOOXOOXXXOOOXXOXXOXOOXXOOXO XOOXOOXXOXXOXOOXOOXOXXXOXXOXOOXOOXXOOXOXXOXXOXOOXOOXOOXXOX XOXOOXXXOOOXXOXOOXXOXXOOOXXXOOOXXOXXOOOOXXXOOXOXXOXOOXOOXX OXOOXXOXXOXOXXOOXXOOXXOOOOXXXOXXOOXXOOOOXXOXXXOOXXOOOXXXOO OOXOXOXXOXXOXXOXOXOOOOXXXOOXXOXOOXXOXXOXOOXOOXOOXXOXOOXXOX XOXOOXXOOXOXOOXOXOXOXXXXOOOXOXOXXOOXOOXOXOXOXXOXOXXXOOXOXO OXOOXOXXXOOXOXXXOOOXXOXOOXOOXXOXXOOXXOOOXXOXOXXOOXXOXOOOXO XXOXOOXOXXOOXXOXOOXXOXOOXOXXXOXOOXXOOXOXOXXXOOXOXOOXXOXXOX OOXOOXOXXOOOXOXXOXOXXOOXXOXOOXXXOXOOOOXXOOXOXXOXOXXOOXXOXO OXXOXOXXOOXXOXOOOXOXXOXOOXXXOOOOXOXOXXOOXXOXOOXXOXXOXXOXOO XOOXOOXXXXOOOXXOOOXOXOXXOXOXXXOOXOXXOOXOXOOXOXOXXOOOXXXOXX 2016, 森棚教官 -- ********************************* * 雄壯威武嚴肅剛直安靜堅強 * * 確實速捷沉著忍耐機警勇敢 * * 我是教官教官是我 * * 每個人都記嘉獎一支 * ********************************* -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.122.140.77 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1479738112.A.AF2.html

推

turboho

11/21 22:29, , 1^F

11/21 22:29, 1^F

推

Desperato

11/21 22:30, , 2^F

11/21 22:30, 2^F

推

llrabel

11/21 23:56, , 3^F

11/21 23:56, 3^F