- 專欄
文章專區
2016-08-01艾狄胥的偏移問題
560 期
Author 作者
游森棚／任教於臺灣師範大學數學系及空軍官校。
最近10年「匈牙利風格」的組合數學有非常豐碩的進展。匈牙利風格組合數學的關鍵人物之一是一生行事都非常戲劇化的艾狄胥（Pál Erdos）。1996年過世的艾狄胥，原創性與對整數的敏感異於常人，他提出了非常多的猜想，其中還是有許多猜想至今懸疑數十年沒有進展。但這幾年有幾個非常有名的艾狄胥問題被解決了。這個月我們介紹的是「艾狄胥的偏移問題（The Erdos 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的安全字串。也就是說，不管這個字串長得怎樣（共有212=4096種可能），綁匪一定找到一個讀法，讓你掉下懸崖。以上就是艾狄胥偏移問題的簡單情形。接下來我們慢慢把問題數學化。如果懸崖兩邊寬一點，比如說在±3掉下懸崖。則12步是有安全字串的，事實上，甚至走100步也有安全字串，讀者能設計出來嗎？這裡給讀者一個極困難的挑戰，此時最長的安全字串有多長？繼續讀下去就知道這個看起來不怎麼樣的問題實際上有多困難。
換個角度想，如果懸崖的兩邊都非常遠，那直覺上，安全字串就可以非常長了。那，是不是有一個無限長度的安全字串呢？比如說，懸崖兩邊都距離原點100萬步。那有沒有一個無限長度的字串，讀1、2、3⋯⋯；或2、4、6⋯⋯；或3、6、9⋯⋯；或4、8、12⋯⋯等，都不會掉到懸崖下？艾狄胥猜「沒有這種無限字串」。1932年，他猜測，不管懸崖兩邊有多遠，則任意一個無限長度的字串，一定可以找到一個讀法讓你掉下懸崖。就是說，任何一個無限長度的字串，「偏移」的程度都可以無限大。......【更多內容請閱讀科學月刊第560期】