作者Giawgwan (教官)
看板Math
标题[其他] Erd"os 的偏移问题
时间Mon Nov 21 22:21:50 2016
最近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/cn.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