小乐数学科普：动漫迷们是如何偶然发现数学证明的——译自Scientific American科学美国人

当某部热门动漫剧集的粉丝想要以各种可能的顺序观看剧集时，他们提出了一个让组合数学家困惑多年的问题。

经典动漫剧集的粉丝们希望知道：

需要多长时间才能以尽可能高的效率

按所有可能的顺序观看一部14集的动漫。

图源：Yuriko Nakao/Getty Images

点击zzllrr小乐公众号主页右上角设为星标★数学科普不迷路！

作者：Manon Bischoff 编辑：Daisy Yuhas 2025-3-3

译者：zzllrr小乐（数学科普公众号）2025-3-19

数学问题的答案可以在意想不到的地方找到，包括互联网的黑暗领域。2011年，一位匿名发帖者在如今臭名昭著、备受争议的图片板4chan上提出了一个关于经典动漫剧集《凉宫春日的忧郁》（The Melancholy of Haruhi Suzumiya）的数学难题。尽管这个公告板上充斥着仇恨、暴力和极端的内容，但最初的帖子却为这个复杂的数学问题提供了解决方案。

这部动漫剧集的第一季共有14集，你可以按照自己喜欢的顺序观看。（对于像我一样不熟悉动漫世界的人来说：Netflix上的一部名为《万花筒》（Kaleidoscope）的8集真人惊悚片也遵循了同样的原则。）在2011年4chan上关于该剧集的讨论中，有人问他们至少要看多少集才能以所有可能的顺序观看。

事实上，这个问题与所谓的超排列（superpermutation）有关。事实证明，这个数学领域存在许多难题：直到今天，数学家仍然无法完全回答4chan用户提出的问题。

但令人惊讶的是，在那次讨论中，一位匿名用户用一种数学家以前不知道的方法估算了观看所有剧集的最低数量。“我需要在多篇帖子中[详细阐述]这一点。请仔细检查我可能遗漏的任何漏洞，”这位用户写道，他分几个步骤解释了他们是如何得出这个估计的。其他用户随后也提出了这些论点并进行了讨论——但在4chan之外，这些都没有引起任何轰动。似乎没有人注意到。

极度沉迷刷剧

在数学中，两个对象在重新排列或重新组合时会发生置换。例如，你可以将AB置换为BA。如果一部动漫剧集只包含两部分，你可以先看第一集，然后看第二集（1-2），也可以先看第二集，然后看第一集（2-1）。

如果你想以多种方式观看一部电视剧（也许是为了弄清楚哪种剧集顺序最合理），你需要一个超排列。这是所有可能排列的序列。想象一下一场马拉松式的节目，你先看第一集，然后看第二集，然后看第二集，再看第一集（1-2-2-1）。为了避免连续两次观看第二集，较短的超排列将是1-2-1；你只需要看三集就可以涵盖所有可能的顺序。

如果一部剧集由三集组成，那么找到最短的超排列就会变得有点棘手。在这种情况下，有 3!=6 个不同的序列：1-2-3、1-3-2、2-3-1、2-1-3、3-1-2、3-2-1。

幸运的是，你不必观看3×6=18集，但可以找到一个巧妙的捷径，在这种情况下：1-2-3-1-2-1-3-2-1。该顺序包含数字1、2和3的所有可能排列，即你只需观看9集!

数学家还计算了由n=4和n=5集组成的剧集的最短超排列（分别为33集和153集）。然而，除此之外，他们一无所知。n>5的最短超排列尚不清楚。

事实上，这个挑战与算法中最难解决的问题之一有关：旅行商问题（TSP - Traveling Salesperson Problem，也称旅行推销员问题）。在这个问题中，一个人想要访问不同的城市，最后回到家乡。任务是找到连接所有城市的最短路线。

最短超排列是这个问题的一个变体，其中各个排列代表不同的城市。在这种情况下，你通过确定排列的重叠来分配城市之间的不同距离。例如，城市 1-2-3 和 2-3-1 有很大的重叠：第一个排列的最后两位数字与第二个排列的前两位数字匹配，因此它们可以组合成 1-2-3-1。

因此，我们可以在这两个城市之间分配一个短距离。另一方面，1-2-3 和 2-1-3 不重叠。（要查看这两个序列，你必须查看完整的六个部分；没有捷径可走。）因此，这些城市之间的距离很大。

要在排列中找到最短路线，你需要连接重叠最多的排列。只有一个困难：没有已知的算法可以快速解决旅行推销员问题。如果我们处理的是几个城市——或者，在动漫剧集中，是几集——这不是一个主要缺点。但一旦n变大，计算机就会无法完成任务，因为计算时间会随着n呈指数增长。

计算机能够计算 n=4 和 n=5 的超排列，但无法计算超过这个数字的超排列。尽管可以计算更大数字的复杂超排列，但找到最短的超排列变得更加困难。

因此，专家必须进行估算。例如，有一种算法可以帮助估算n个对象的最短超排列的长度：1!+2!+3!+ ⋯ +n! 使用该算法，如果n=2，则得到长度为 1+2=3 的超排列。对于n=3，结果长度为 1+2+6=9。对于n=4，结果为33。对于n=5，结果为153，这对应于每种情况下的最短超排列。

然而，对于较大的n，此算法不再适用：计算机已经能够找到比它所推导的更短的超排列。事实上，公式1!+2!+3!+ ⋯ +n!大大高估了较大的n的最短超排列的长度。尽管该算法仅提供近似答案，但数学家将其作为起点，目的是缩小可选范围以找到更精确的答案。

巧合与重新发现

2013年，现任新不伦瑞克省蒙特艾利森大学数学教授的纳撒尼尔·约翰斯顿（Nathaniel Johnston）浏览了《凉宫春日的忧郁》粉丝页面。约翰斯顿本人并不是动漫迷。他是在谷歌搜索一些与超排列相关的搜索词后进入该网站的。在那里，他偶然发现了近两年前在 4chan 上的讨论，一名用户将其复制到了粉丝网站上。

约翰斯顿没有费心去计算，只是在他的博客上引用了粉丝的帖子。http://www.njohnston.ca/2013/04/the-minimal-superpermutation-problem/ 这条评论在几年内也没有被注意到。

2018年10月，数学家罗宾·休斯顿（Robin Houston）偶然看到了同事的博客文章。休斯顿刚刚得知，澳大利亚科幻小说作家格雷格·伊根（Greg Egan）发现了最短超排列的新最大长度，表示为：

n!+(n-1)!+(n-2)!+(n-3)!+n-3

这本身就很奇怪。但当休斯顿开始进一步了解这个结果时，他意识到超排列的最小长度已被一位匿名动漫粉丝赋予了一个新值（他当时不知道 4chan 上的起源）。最小长度的公式为：

n!+(n-1)!+(n-2)!+n-3

同年10月23日，休斯顿在Twitter（现为X https://x.com/robinhouston/status/1054637891085918209）上分享了他的发现。“这真是一个奇怪的情况。超排列最小长度的最优下限是由一位主要关注动漫的维基匿名用户证明的，https://mathsci.fandom.com/wiki/The_Haruhi_Problem ”他写道。

休斯顿与他的同事、数学家杰伊·潘通（Jay Pantone）和文斯·瓦特（Vince Vatter）一起决定检查 4chan 用户的证明，并将其以数学方式记录下来。研究人员于同月将他们的数学工作发布到整数序列在线百科全书OEIS https://oeis.org/A180632/a180632.pdf ，第一作者被列为“匿名 4chan 发帖者”。

那么这些公式告诉我们什么呢？如果你想以所有可能的组合观看一部n集剧集，你必须至少看完n!+(n-1)!+(n-2)!+n-3 集（这是4chan用户的贡献），最多看完n!+(n-1)!+(n-2)!+(n-3)!+n-3集，这是我们通过 Egan 的工作知道的。

对于8集的连续剧《万花筒》，你至少要看46085集，最多要看46205集。对于14集的《凉宫春日的忧郁》，这个数字急剧增加：最少 93884313611 集，最多 93924230411 集。

回想一下，这不是一个完整的解——它只是为超排列的大小设置了一个范围，让你能够以任何可能的顺序高效地观看该剧集。

幸运的是，Egan 还提供了一个构建相应超排列的算法。这让《春日》（Haruhi）粉丝们能够找出最佳的剧集观看顺序。但考虑到每集平均长度约为24分钟，观看完这个超排列需要大约400万年。

参考资料

https://www.scientificamerican.com/article/the-surprisingly-difficult-mathematical-proof-that-anime-fans-helped-solve/

http://www.njohnston.ca/2013/04/the-minimal-superpermutation-problem/

https://x.com/robinhouston/status/1054637891085918209

https://mathsci.fandom.com/wiki/The_Haruhi_Problem

https://oeis.org/A180632/a180632.pdf

科普荐书

【更多读者好评数学书单推荐、数学科普作家自荐、出版社书单推荐通道已陆续打开，敬请期待】

·开放 · 友好 · 多元 · 普适 · 守拙·

让数学

更加

易学易练

易教易研

易赏易玩

易见易得

易传易及

欢迎评论、点赞、在看、在听

收藏、分享、转载、投稿

查看原始文章出处

点击zzllrr小乐

公众号主页

右上角

数学科普不迷路！