一篇匿名的4chan帖子帮助解决了一个25年前的数学难题

2011年9月16日，一名动漫迷在网上公告栏4chan上发布了一道数学题，内容是关于邪教经典电视剧铃宫春日的忧郁。这部剧的第一季涉及时间旅行，最初是按时间顺序播出的，重播和DVD版本都进一步重新安排了这两集。粉丝们在网上就观看剧集的最佳顺序争论不休，4chan的海报想知道：如果观众想以每一个可能的顺序看这部电视剧，他们必须看的最短的剧集名单是什么？

在不到一个小时的时间里，一位匿名人士给出了答案--不是一个完整的解决方案，而是一个所需剧集数量的下限。这场争论涵盖了任何数量的连续剧，结果显示，对于14集的第一季来说，观众必须至少观看93,884,313,611集才能看到所有可能的顺序。这位匿名发帖者写道：“请检查(证据)是否有我可能遗漏的任何漏洞。”

这个证明在七年的时间里一直没有受到数学界的关注--显然当时只有一位专业数学家发现了它，而且他没有仔细检查。但在上个月的情节转折中，澳大利亚科幻小说家格雷格·伊根(Greg Egan)证明了所需剧集数量的新上限。伊根的发现重新引起了人们对这个问题的兴趣，并引起了人们对2011年匿名发布的下限的关注。这两个证明现在都被誉为在一个数学家研究了至少25年的难题上取得了重大进展。

数学家很快验证了伊根的上界，它和下界一样，适用于任何长度的级数。然后，数据可视化公司Kiln的数学家罗宾·休斯顿(Robin Houston)和密尔沃基马凯特大学(Marquette University)的杰伊·潘通(Jay Pantone)独立核实了匿名4chan海报的工作。Pantone说，“要想弄清楚这是否正确，需要做大量的工作，”因为关键的观点并没有特别清晰地表达出来。

现在，休斯顿和潘通，以及盖恩斯维尔的佛罗里达大学的文斯·瓦特，已经写下了正式的论点。在他们的论文中，他们将第一作者列为“匿名4chan海报”。

如果一部电视剧只有三集，那么有六种可能的观看顺序：123、132、213、231、312和321。你可以把这六个序列串在一起，给出一个18集的列表，其中包括每一次的排序，但有一个更有效的方法：123121321集。这样的序列包含n个符号集合的每个可能的重新排列(或排列)，称为“超排列”。

1993年，丹尼尔·阿什洛克(Daniel Ashlock)和杰内特·蒂洛森(Jenett Tillotson)观察到，如果你观察不同n值的最短超排列，似乎很快就会出现一种涉及阶乘的模式-那些以n！形式写成的数字，涉及将所有数字相乘到n(例如，4！=4×3×2×1)。

如果你的连续剧只有一集，那么最短的超排列长度是1！(也称为普通老式1)。对于两集的连续剧，最短的超排列(121)的长度是2！+1！。对于三集(我们上面看到的例子)，长度是3！+2！+1！，对于四集(123412314231243121342132413214321)，长度是4！+3！+2！+1！。超排列的阶乘法则成了传统智慧(尽管没有人能证明n的每一个值都是正确的)，数学家后来证实了n=5。

然后在2014年，休斯顿证明了当n=6时，模式被打破，这让数学家们大吃一惊。析因法则预测，以每种可能的顺序观看6集应该需要873集，但休斯顿找到了一种方法，在872集就可以做到这一点。由于有一种简单的方法可以将n个符号上的短超置换转换为n+1个符号上的短超置换，因此休斯顿的例子意味着阶乘规则对于n的每一个大于6的值也是无效的。

休斯顿的建筑工作是通过将超排列问题转化为著名的旅行商问题来进行的，该问题寻找通过一系列城市的最短路线。更具体地说，超排列与“不对称”旅行商问题有关，在这个问题中，两个城市之间的每条路径都有一个成本(两个方向不一定相同)，目标是找到穿越所有城市的最便宜的路线。

翻译很简单：把每个排列想象成一个“城市”，想象一条从每个排列到彼此排列的路径。在超排列问题中，我们需要列出所有排列的尽可能短的数字序列，因此目标是以在开始排列中添加尽可能少的数字的方式遍历排列。所以我们声明每条路径的开销就是我们必须附加到第一个排列的末尾才能得到第二个排列的位数。例如，在n=3的示例中，从231到312的路径成本为1美元，因为我们只需在231的末尾加上2即可得到312，而从231到132的路径成本为2美元，因为我们必须添加32。在这种设置下，穿过城市的最便宜的路径直接对应于最短的超排列。

这个翻译意味着休斯顿可以把旅行推销员算法的力量用在超排列问题上。旅行商问题是著名的NP-hard问题，也就是说没有一个有效的算法可以解决所有情况。但是有一些算法可以有效地解决某些情况，还有一些算法可以产生很好的近似解。休斯顿使用后者中的一个来产生他的872位超排列。

由于他只产生了一个近似解，这可能不是最好的超排列。潘通说，数学家们现在正在进行一个巨大的计算机搜索，以寻找六个符号上的最短超排列。“我们知道我们的搜索将在有限的时间内完成，但不知道那是一周还是一百万年，”他说。“没有进度条。”

到休斯顿工作的时候，这篇匿名的4chan帖子已经在互联网的角落里呆了近三年了。艾利森山大学(Mount Allison University)的数学家纳撒尼尔·约翰斯顿(Nathaniel Johnston)在帖子发布几天后，在另一个网站上注意到了一份副本--不是因为他是动漫迷，而是因为他在谷歌(Google)输入了一系列与超排列相关的搜索词。

约翰斯顿读了这一论点，认为这似乎是合理的，但他并没有投入太多精力仔细检查。当时，数学家认为超排列的阶乘公式可能是正确的，当你认为你知道一个问题的确切答案时，下限并不是很有趣。换句话说，超排列研究的情节正在打乱顺序。

约翰斯顿后来在几个网站上提到了下限，但“我认为没有人真的特别注意到这一点，”休斯顿说。

今年9月26日，加州大学河滨分校(University of California，Riverside)的数学家约翰·贝兹(John Baez)在Twitter上发布了休斯顿2014年的发现，这是一系列关于明显数学模式失败的推文的一部分。他的推文引起了伊根的注意，伊根几十年前还是一名数学专业的学生，后来他开始了科幻小说家的获奖职业生涯(他1994年的突破性小说被命名为置换城市，这是一个令人高兴的巧合)。“我从未停止过对(数学)的兴趣，”伊根在电子邮件中写道。

伊根想知道是否有可能构建比休斯顿的更短的超排列。他在文献中搜寻关于如何通过排列网络构建短路径的论文，几周后就找到了他所需要的。在一两天之内，他给出了n个符号的最短超置换长度的一个新的上界：n！+(n-1)！+(n-2)！+(n-3)！+n-3。它类似于旧的阶乘公式，但去掉了很多项。

与此同时，这张匿名的4chan海报的下限非常接近新的上限：它计算出的结果是n！+(n-1)！+(n-2)！+n-3。当伊根的结果公之于众时，约翰斯顿提醒其他数学家关于匿名海报的证明，休斯顿和潘通很快证明了这一点是正确的。与休斯顿的工作一样，通过旅行商问题，新的下界和上界都是超排列的：下界表明，通过所有城市的路线必须沿着成本超过1美元的最小数量的路径行驶，而上界则为每个n个只使用1美元和2美元连接的路径构建一条特定的路线。

对于Haruhi的粉丝来说，Egan的结构给出了明确的指导，告诉他们如何在93,924,230,411集内观看第一季的所有可能的点播。观众可以立即开始疯狂观看，或者他们可以等着看数学家是否能削减这个数字。这位匿名海报的下限证明，这种削减不可能节省超过4000万集-但这足以在第二季有一个良好的开端。

最初的故事经广达杂志许可转载，广达杂志是西蒙斯基金会的一份编辑独立的出版物，其使命是通过报道数学、物理和生命科学的研究发展和趋势来加强公众对科学的理解。

长寿的关键与“好基因”没有多大关系。

还想要更多吗？订阅我们的每日时事通讯，永远不会错过我们最新最精彩的故事