锚点111
一位动漫迷在4chan上抛出问题：怎样用最少集数看遍《凉宫春日的忧郁》的所有排列顺序？这一问题竟引发了一场数学探索之旅，揭开了超排列难题的全新解法。
不妨想象一下，你身为动漫迷，痴迷于《凉宫春日的忧郁》第一季的14集。这部剧的独特之处在于，各集之间的观看顺序可以随意调换。于是，你突发奇想：要将所有可能的排列都看一遍，最少需要观看多少集呢？这个看似简单的问题，在2011年的4chan论坛上，引发了一场意想不到的数学冒险。
就在那一年，一位匿名用户在4chan上提出了这个疑问。尽管该论坛后来因极端内容而声名狼藉，但那次讨论却犹如草丛中的明珠。有人开始认真思考：14集能有多少种排列方式？要涵盖所有顺序，最短的“播放列表”长度是多少？实际上，这正是数学领域中的“超排列”问题——一个令组合数学家们头疼不已的难题。
超排列究竟是什么呢？举例来说，假设只有两集，分别标记为1和2。观看顺序可以是1 – 2，也可以是2 – 1。要包含这两种顺序，最短的超排列是1 – 2 – 1，只需3集。当集数增加到3集时，可能性变为3! = 6种，比如1 – 2 – 3、1 – 3 – 2、2 – 1 – 3等等。一个巧妙的序列1 – 2 – 3 – 1 – 2 – 1 – 3 – 2 – 1，9集就足以涵盖所有情况。数学家们还计算出，4集和5集的最短超排列分别是33集和153集。然而，一旦集数超过5集，比如14集，情况就变得复杂起来。数学家们虽然已经算出4集和5集的最短超排列，但当集数更多时，他们也只能摸索前行。
那个4chan用户的问题，恰好击中了这个尚未解决的谜团。更令人惊奇的是，在那场讨论中，一位匿名网友竟然提出了一个全新的思路。他写道：“我得发几个帖子来解释，请帮我找找其中的漏洞。”他一步步进行推导估算，其他人也接力参与讨论，气氛热烈非凡。可惜的是，这场智慧的碰撞仅在小范围内流传，外界并未关注到。
事情并未就此结束。超排列问题实际上与“旅行推销员问题”相关，就如同要寻找一条最短路线遍历所有城市一样。排列之间的“距离”由重叠情况决定，例如1 – 2 – 3和2 – 3 – 1能够衔接成1 – 2 – 3 – 1，这种情况下距离较短；而1 – 2 – 3和2 – 1 – 3没有重叠部分，距离则较长。随着集数的增加，计算量会急剧增长，甚至连电脑都难以承受。数学家们常用1! + 2! + 3! +… + n!来进行估算，比如当n = 5时，结果是153集，但当n更大时，计算量会呈爆炸式增长。
尽管如此，那位4chan网友的估算仍然让人眼前一亮。到了2013年，数学家Nathaniel Johnston偶然在粉丝网站上看到了这段讨论。他并非动漫爱好者，只是在搜索超排列相关内容时误打误撞进入此地。他在博客上简单提及了此事，没想到五年后，这件事才有了后续发展。2018年，数学家Robin Houston通过同事的博客发现了它。当时，他刚刚得知澳洲作家Greg Egan提出了超排列的最长公式：n! + (n – 1)! + (n – 2)! + (n – 3)! + n – 3。而那位4chan网友的估算，给出了最短范围：n! + (n – 1)! + (n – 2)! + n – 3。
Houston在Twitter上惊叹道：“一个动漫迷竟然证明了超排列的最优下限，这太不可思议了！”他和同事Jay Pantone、Vince Vatter将这个发现整理成论文，署名的第一作者是“匿名4chan用户”。按照这个公式，8集的《万花筒》至少要看46,085集，最多46,205集；14集的《凉宫春日》，则从93,884,313,611集到93,924,230,411集。假设每集时长为24分钟，全部看完大约需要400万年。
从动漫迷的随意一问，到成功破解数学难题，这场意外之旅告诉我们：灵感有时就隐藏在最不引人注意的地方。Egan还贴心地给出了一个算法，方便《凉宫春日》的粉丝规划观影顺序。可惜的是，面对这长达400万年的“马拉松”，又有谁有足够的耐心看完呢？
本文译自 Scientific American，由 BALI 编辑发布。
