Math 板


LINE

最近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://webptt.com/m.aspx?n=bbs/Math/M.1479738112.A.AF2.html
1F:推 turboho : 頭推 11/21 22:29
2F:推 Desperato : 推推 11/21 22:30
3F:推 llrabel : 感謝大大分享 11/21 23:56
4F:推 LeonYo : 頸推!! 文章看到一半回頭看果然是教官! 11/22 00:01
5F:推 OppOops : 感謝分享 11/22 00:37
6F:推 HeterCompute: 推教官 11/22 03:01
7F:推 Sfly : 好文 11/22 13:29
8F:推 coolbetter33: 我們普通人還是解決 ±2 就好 XD 11/22 13:40
9F:推 jacky7987 : 推 11/22 14:42
10F:推 Uniqueness : 教官推 11/22 18:15
11F:推 jack7775kimo: 推! 11/22 19:21
12F:推 G41271 : 推 11/22 19:30
13F:推 changkui : 看到教官 先推個! 11/22 20:49
14F:推 mike34159 : 潛水潛太久 看到教官這篇就浮起來了ww 11/22 21:18
15F:推 paulneyo : 推!!! 11/22 21:44
16F:推 lovedjan : 推教官 11/22 22:54
17F:推 Panthalassa : 好文推 11/23 01:31
18F:推 pentiumevo : 推教官! 11/23 01:39
19F:推 TassTW : 未看先推教官 11/23 04:10
20F:推 a016258 : 推 11/23 09:34
21F:推 NoireIan : 教官 11/23 09:53
22F:推 softseaweed : 11/23 13:11
23F:推 giraffe1021 : 感謝分享 蠻有趣的 11/23 14:01
24F:推 josh28 : 推! 11/24 16:08
25F:→ buffalobill : 如果綁匪可以倒著數(11,10,9...)(11,9,7...)的話 11/24 23:36
26F:→ buffalobill : C=2的安全字串會有多長呢? 11/24 23:36
27F:→ Giawgwan : 好問題, 直覺上會大幅縮減 11/25 09:59
28F:推 Vulpix : 推! 11/25 12:08
29F:→ buffalobill : 寫了程式去算,可以倒著數的話安全長度只剩下8 11/28 11:04
30F:→ buffalobill : 比如OXXOXOOX,你後面不管加O或X都會破功 11/28 11:04
31F:推 y956403 : 推有趣 11/28 12:44
32F:→ buffalobill : 然後C=2時拿1160的答案去正反跑,發現只有前26位有效 11/28 20:25
33F:推 HmmHmm : 推教官 11/29 01:28
34F:→ Giawgwan : 被 HmmHmm 推, 頗為驚喜~ 03/31 16:40







like.gif 您可能會有興趣的文章
icon.png[問題/行為] 貓晚上進房間會不會有憋尿問題
icon.pngRe: [閒聊] 選了錯誤的女孩成為魔法少女 XDDDDDDDDDD
icon.png[正妹] 瑞典 一張
icon.png[心得] EMS高領長版毛衣.墨小樓MC1002
icon.png[分享] 丹龍隔熱紙GE55+33+22
icon.png[問題] 清洗洗衣機
icon.png[尋物] 窗台下的空間
icon.png[閒聊] 双極の女神1 木魔爵
icon.png[售車] 新竹 1997 march 1297cc 白色 四門
icon.png[討論] 能從照片感受到攝影者心情嗎
icon.png[狂賀] 賀賀賀賀 賀!島村卯月!總選舉NO.1
icon.png[難過] 羨慕白皮膚的女生
icon.png閱讀文章
icon.png[黑特]
icon.png[問題] SBK S1安裝於安全帽位置
icon.png[分享] 舊woo100絕版開箱!!
icon.pngRe: [無言] 關於小包衛生紙
icon.png[開箱] E5-2683V3 RX480Strix 快睿C1 簡單測試
icon.png[心得] 蒼の海賊龍 地獄 執行者16PT
icon.png[售車] 1999年Virage iO 1.8EXi
icon.png[心得] 挑戰33 LV10 獅子座pt solo
icon.png[閒聊] 手把手教你不被桶之新手主購教學
icon.png[分享] Civic Type R 量產版官方照無預警流出
icon.png[售車] Golf 4 2.0 銀色 自排
icon.png[出售] Graco提籃汽座(有底座)2000元誠可議
icon.png[問題] 請問補牙材質掉了還能再補嗎?(台中半年內
icon.png[問題] 44th 單曲 生寫竟然都給重複的啊啊!
icon.png[心得] 華南紅卡/icash 核卡
icon.png[問題] 拔牙矯正這樣正常嗎
icon.png[贈送] 老莫高業 初業 102年版
icon.png[情報] 三大行動支付 本季掀戰火
icon.png[寶寶] 博客來Amos水蠟筆5/1特價五折
icon.pngRe: [心得] 新鮮人一些面試分享
icon.png[心得] 蒼の海賊龍 地獄 麒麟25PT
icon.pngRe: [閒聊] (君の名は。雷慎入) 君名二創漫畫翻譯
icon.pngRe: [閒聊] OGN中場影片:失蹤人口局 (英文字幕)
icon.png[問題] 台灣大哥大4G訊號差
icon.png[出售] [全國]全新千尋侘草LED燈, 水草

請輸入看板名稱,例如:Soft_Job 或 站內搜尋

TOP