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

[Giawgwan (教官)]

最近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     : 頭推
推 Desperato   : 推推
推 llrabel     : 感謝大大分享
推 LeonYo      : 頸推!! 文章看到一半回頭看果然是教官!
推 OppOops     : 感謝分享
推 HeterCompute: 推教官
推 Sfly        : 好文
推 coolbetter33: 我們普通人還是解決 ±2 就好 XD
推 jacky7987   : 推
推 Uniqueness  : 教官推
推 jack7775kimo: 推!
推 G41271      : 推
推 changkui    : 看到教官 先推個！
推 mike34159   : 潛水潛太久 看到教官這篇就浮起來了ww
推 paulneyo    : 推!!!
推 lovedjan    : 推教官
推 Panthalassa : 好文推
推 pentiumevo  : 推教官！
推 TassTW      : 未看先推教官
推 a016258     : 推
推 NoireIan    : 教官
推 softseaweed :
推 giraffe1021 : 感謝分享 蠻有趣的
推 josh28      : 推！
→ buffalobill : 如果綁匪可以倒著數(11,10,9...)(11,9,7...)的話
→ buffalobill : C=2的安全字串會有多長呢？
→ Giawgwan    : 好問題, 直覺上會大幅縮減
推 Vulpix      : 推！
→ buffalobill : 寫了程式去算，可以倒著數的話安全長度只剩下8
→ buffalobill : 比如OXXOXOOX，你後面不管加O或X都會破功
推 y956403     : 推有趣
→ buffalobill : 然後C=2時拿1160的答案去正反跑,發現只有前26位有效
推 HmmHmm      : 推教官
→ Giawgwan    : 被 HmmHmm 推, 頗為驚喜~