自古评论出人才，这不澳大利亚科幻作家格雷格·伊根(Greg Egan)提出的一项新证明，以及2011年匿名发布在网上的新证明被科学家誉为是解决一个至少有25年研究历史的谜题的重大突破口。2011年9月16日一位动漫迷在网上布告栏4chan上发布了一个关于狂热崇拜宗教经典电视剧《Haruhi Suzumiya》的数学问题。第一季的节目，包括时间旅行，最初以非时间顺序播出，重播和DVD版本的每进一步都重新安排片段。粉丝们正在网上讨论观看这些剧集的最佳顺序，4chan的发布者想知道：如果观众想以各种可能的顺序观看该剧，他们观看的最短剧集列表是怎样的？
博科园-科学科普：在不到一小时的时间里，一位匿名的人给出了一个答案，这个解决方案算不上完整，并且需要剧集数量的下限。这场争论涵盖了任意数量的剧集，匿名者表明，对于《Haruhi Suzumiya》第四季的14集来说，观众至少要看938.84313611亿个片段才能看到所有可能出现的排序，这位匿名发帖者写道：请仔细检查证明过程，看看我是否漏掉了什么重要信息”。
匿名者的证明在数学学界被埋藏了7年之久，虽然当时有一位专业数学家发现了它，但他却没有仔细检查证明过程。在上个月，澳大利亚科幻小说家格雷格·伊根的发现重新激起了人们对这个问题的兴趣，并引起了人们对2011年匿名发布的下限问题的关注。
图片：Maciej Rebisz for Quanta Magazine
数学家们很快验证了伊根的上界和下界一样，适用于任何长度的级数。随后，数据可视化公司Kiln的数学家罗宾•休斯顿(Robin Houston)和密尔沃基马凯特大学(Marquette University)的杰伊•潘通(Jay Pantone)独立证明了4chan匿名发布者的计算结果：我们花了很多功夫才弄清楚它是否正确。现在休斯顿和潘通，以及位于盖恩斯维尔的佛罗里达大学的文斯·瓦特斯，已经写了正式的论点。在论文中，他们将第一作者列为“匿名4chan的发布者”。是一种很奇怪的情况，如此简练的证明竟被张贴在如此不为人知的地方。
1、排列城市
如果一部电视剧只有三集，那么观众可以选择六种观看顺序：123、132、213、231、312和321。你可以把这六个序列串在一起，得到一个18集的列表。虽然其中包含了所有的排序，但是123121321这样的排序方法更为有效，这样一个序列包含了n个符号集合的所有可能重排(或排列)，被称为“超排列”。在1993年，丹尼尔·阿什洛克 和詹尼特·蒂洛森发现，如果观察不同n值的最短超排列，很快就会发现一个包含阶乘的模式——那些用n表示的数字！这涉及到将所有的数字相乘直到n：例如，4!= 4×3×2×1。如果系列只有一集，那么最短的超排列长度是1!(也被称为plain old 1)对于两集的电视剧，最短的超排列长度是2!+ 1 !；对于三集长度是3集!+ 2 !+ 1 !；四集是4!+ 3 !+ 2 !+ 1 !。
超级排列的阶乘规则成为了传统智慧(尽管没有人能证明它对应的每个n值都正确)，数学家后来在n = 5时证实了这一点。2014年休斯顿让数学家们震惊地发现当n = 6时，这一模式就走向崩溃。阶乘规则预测，每一种顺序看6集需要873个片段，但休斯顿在872处找到了一种方法，可以将n个符号上的超置换变换转换成n + 1个符号上的超置换变换，休斯顿的方法意味着阶乘规则对n以上的每一个值都失效。休斯顿的建筑工作是将超级排列问题转化为著名的旅行推销员问题——寻找穿过一系列城市的最短路线。更具体地说，超级排列与“不对称”的旅行推销员问题有关，在这个问题中，两个城市之间的每条路径都有成本(两个方向不一定相同)，所以就要找到贯穿所有城市的最便宜的路线。
这种转换非常简单:把每个排列想象成一个“城市”，想象从一个排列到另一个排列的路径。在超级排列问题中，想要列出所有排列可能的最短数字序列，就要通过在开始排列时增加尽可能少的数字来进行排列。因此每条路径的代价就是我们要在第一个排列的末尾附加位数来得到第二个排列。例如在n = 3的例子中，从231到312的路径花费1美元，因为我们只需要在231的末尾加一个2就能得到312，而从231到132的路径花费2美元，因为我们必须加一个32。通过这种设置，通过城市最便宜的路径直接对应于最短的超级排列。
图片：Lucy Reading-Ikkanda/Quanta Magazine
这种转换意味着休斯敦可以把旅行商算法的能力转化为超排列问题。旅行商问题是一个NP-hard问题，意思是没有有效的算法可以解决它的所有情况。但是，有一些算法可以有效地解决一些情况，以及其他算法产生良好的近似解。休斯敦使用后者中的一个来产生他的872位超排列。因为他只给出了一个近似解，所以它可能不是最好的超置换，数学家们正在用巨大的计算机搜索六个符号中最短的超排列。我们知道的搜寻将在有限时间内完成，但不知道是一周还是100万年。
2、错误的命令
到休斯敦开始研究时，匿名的4Chan-Press已经在互联网角落里等待了将近三年。山埃里森大学的数学家纳撒尼尔·约翰斯顿，在帖子发布几天后，在另一个网站上注意到了一份复制品，注意到这份帖子不是因为他是动画迷，而是因为他在Google中输入了一系列与超级排列相关的搜索词。约翰斯顿读了这个论点之后认为它有一定的合理性，但没有投入太多精力仔细检查它。当时数学家们认为超级排列的阶乘公式可能正确，当你认为你知道一个问题的确切答案时，下界这一条件并不引人注意。换句话说，超级排列研究的插曲不合顺序。约翰斯顿后来在几个网站上提到了下界，但休斯顿说：我认为没有人会特别注意它。
今年9月26日加州大学河滨分校(University of California, Riverside)数学家约翰·贝兹(John Baez)在Twitter上发布了一篇关于休斯顿2014年发现的文章，并引起了伊根的注意。几十年前，伊根还是数学专业的学生，在那之前，他以科幻小说家的身份开创了一份屡获殊荣的职业，我从未停止过对数学的兴趣。伊根想知道是否有可能构建比休斯顿更短的超级排列。他在文献中寻找关于如何通过排列网络构建短路径的论文，几周后他就找到了他需要的东西。一两天之内，就提出了一个新的上限，即n个符号的最短超排列的长度:n!+ (n - 1)!+ (n - 2)!+ (n - 3)!+ n - 3。它类似于旧的阶乘公式，但是项数变少了，它绝对打破了以前的上限。与此同时4chan匿名的发布者的下界与新上界惊人地接近:n!+ (n - 1)!+ (n - 2)!+ n - 3。
当Egan的结果公开后，约翰斯顿提醒其他数学家关注匿名发布者的证明，而休斯敦和潘通很快证明了它是正确的。引用休斯顿的转换思维：下界显示的路线通过所有的城市必须沿着一些最低成本的路径数量超过1美元，而每个n的上界构造特定的路线，只使用1美元和2美元连接。研究人员现在正试图将上界和下界结合起来，找到一个解决超排列问题的单一公式。贝兹预测：也许人们最终会完全解开这个谜团，现在看起来不错。对于Haruhi的粉丝来说，伊根的构建给出了明确指导，告诉他们如何在93,924,230,411片段里观看第一季所有可能的排序。观众可以立即开始狂看，或者等着数学家是否能把这个数字削减下来。匿名发布者证明了这种缩减不可能拯救超过4000万片段的剧情，但这足以让第二季有个不错的开始。
博科园-科学科普｜公开论文截图来自：docs.google
文：Erica Klarreich/Quanta magazine/Quanta Newsletter
发表于 2018-11-14 07:24
收藏
分享