动漫迷偶然发现的数学证明：Superpermutation 问题
Skip to main content Scientific American 2025年3月3日 阅读时长：6分钟
动漫迷如何偶然发现一个数学证明
当一部邪典动漫系列的粉丝想要以所有可能的顺序观看剧集时，他们提出了一个困扰组合数学家多年的问题。
作者：Manon Bischoff 编辑：Daisy Yuhas
一部经典动漫系列的粉丝试图计算出以所有可能的顺序，尽可能高效地观看一个14集系列需要多长时间。
Yuriko Nakao/Getty Images
数学解题方案可能出现在令人惊讶的地方，包括互联网的黑暗领域。2011年，在如今声名狼藉且极具争议的图片论坛4chan上，一位匿名用户提出了一个关于邪典经典动漫系列《凉宫春日的忧郁 (The Melancholy of Haruhi Suzumiya)》的数学难题。虽然该公告板已经充斥着仇恨、暴力和极端内容，但最初的帖子却促成了对这个复杂数学问题的解决。
这部动漫系列的第一季由14集组成，这些剧集的设计方式让你可以按照任何你喜欢的顺序观看。（对于像我一样不熟悉动漫世界的人来说：Netflix上的一部名为《万花筒 (Kaleidoscope)》的八部分真人惊悚片遵循了同样的原则。）在2011年4chan上对该系列的一次讨论中，有人问到，为了以所有可能的顺序观看，他们必须观看的最少集数是多少。
事实上，这个问题与所谓的superpermutation（超排列）有关。事实证明，这个数学领域包含许多难题：直到今天，数学家仍然无法完全回答4chan用户提出的问题。
关于支持科学新闻报道
如果您喜欢这篇文章，请考虑订阅我们的获奖新闻报道，以支持我们的工作。通过购买订阅，您正在帮助确保有关当今世界中塑造我们的发现和想法的影响性故事的未来。
但令人惊讶的是，在当时的讨论中，一位匿名用户用一种数学家以前不知道的方法，估算出了观看所有剧集所需的最小数量。这位用户写道：“我需要用多个帖子来详细说明这一点。请仔细检查我可能遗漏的任何漏洞”，他分几个步骤解释了他们如何得出估计值。其他用户随后采纳了这些论点并进行了讨论——但在4chan之外，这一切都没有引起任何轰动。似乎没有人注意到。
极限刷剧
在数学中，当两个对象被重新排列或重新组合时，它们会发生排列（permutations）。例如，你可以将AB排列成BA。如果一个动漫系列只包含两个部分，你可以先观看第一集再观看第二集（1-2），或者先观看第二集再观看第一集（2-1）。
如果你想以多种排列方式观看一个系列——也许是为了弄清楚哪一个剧集顺序最有意义——你需要一个superpermutation。这是一个包含所有可能排列的序列。想象一个马拉松式的放映，你先看第一集，然后是第二集，然后再看第二集，再看第一集（1-2-2-1）。为了避免连续两次观看第二集，一个更短的superpermutation将会是1-2-1；你只需要观看三集就可以覆盖所有可能的顺序。
如果一个系列包含三集，找到最短的superpermutation就会变得更加棘手。在这种情况下，有 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 的所有可能排列，但你只需要观看九集！
数学家们还计算出了一个系列包含 n = 4 和 n = 5 集时最短的superpermutation（分别为33集和153集）。然而，除此之外，他们仍然一无所知。n > 5 的最短superpermutation仍然未知。
事实上，这个挑战与算法中最难解决的问题之一有关：旅行推销员问题 (the traveling salesperson problem)。在这个问题中，一个人想要访问不同的城市，最后回到他们的家乡。任务是找到连接所有城市的最短路线。最短的superpermutation是这个问题的一个变体，其中单个排列代表不同的城市。在这种情况下，你通过确定排列的重叠来分配城市之间的不同距离。例如，城市 1-2-3 和 2-3-1 有很大的重叠：第一个排列的最后两位数字与第二个排列的前两位数字匹配，因此它们可以组合成 1-2-3-1。因此，我们可以为这两个城市分配一个较短的距离。另一方面，1-2-3 和 2-1-3 没有重叠。（要查看两个序列，你必须查看完整的六个部分；没有捷径可走。）因此，这些城市之间的距离很大。
为了在排列中找到最短路线，你需要连接重叠最多的排列。只有一个难点：没有已知的算法可以快速解决旅行推销员问题。如果我们处理的是几个城市——或者，在一个动漫系列的情况下，是几集——这不是一个主要的缺点。但是，一旦 n 变得很大，计算机就会在任务中失败，因为计算时间会随着 n 的增加呈指数增长。
计算机能够计算 n = 4 和 n = 5 的superpermutation，但无法计算超出此范围的superpermutation。虽然可以计算出更复杂的较大数字的superpermutation，但找到最短的superpermutation变得更加困难。
因此，专家们必须满足于估计。例如，有一种算法可以帮助估计 n 个对象的最短可能superpermutation的长度：1! + 2! + 3! + ... + n! 使用该算法，如果 n = 2，你会得到一个长度为 1 + 2 = 3 的superpermutation。对于 n = 3，这将导致长度为 1 + 2 + 6 = 9。对于 n = 4，你会得到 33。对于 n = 5，你会得到 153，这与每种情况下的最短superpermutation相对应。
然而，对于较大的 n，此算法不再适用：计算机已经能够找到比它建议存在的superpermutation更短的superpermutation。事实上，公式 1! + 2! + 3! + ... + n! 大大高估了大型 n 的最短superpermutation的长度。虽然该算法仅提供近似答案，但数学家将其用作起点，目标是缩小选项范围以找到更精确的答案。
巧合与再发现
2013年，Nathaniel Johnston（现任加拿大新不伦瑞克省芒特艾利森大学的数学教授）偶然发现了一个《凉宫春日的忧郁 (Melancholy of Haruhi Suzumiya)》的粉丝页面。Johnston本人并不是动漫迷。他在谷歌上搜索了一些与superpermutation相关的搜索词后到达了该网站。在那里，他看到了大约两年前在4chan上进行的讨论，一位用户将其复制到了粉丝网站。
Johnston没有费心进行数学运算，而是在他的博客上引用了粉丝帖子。这条评论也同样多年未被注意到。
然后在2018年10月，数学家 Robin Houston 通过一个奇妙的巧合偶然发现了他的同事的博客文章。Houston刚刚得知澳大利亚科幻小说作家 Greg Egan 找到了最短superpermutation的一个新的_最大_长度，表示为：
n! +(n –1)! + (n – 2)! + (n – 3)! + n – 3
这本身就很奇怪。但是当 Houston 开始更多地了解这个结果时，他意识到一个匿名动漫粉丝用户（当时他不知道它起源于4chan）给出了superpermutation的最小长度的一个新值。最小长度的公式为：
n! +(n – 1)! + (n – 2)! + n – 3
Houston 在当年10月23日在Twitter (现为X) 上分享了他的发现。“一个奇怪的情况。superpermutation最小长度的最佳已知下限是由一个主要致力于动漫的维基的匿名用户证明的，”他写道。
与他的同事，数学家 Jay Pantone 和 Vince Vatter 一起，Houston 决定检查4chan用户的证明，并以数学的方式将其写下来。研究人员同月将他们的数学工作发布到了整数数列在线百科全书中，第一作者被列为“Anonymous 4chan Poster”。
那么这些公式告诉我们什么呢？如果你想以所有可能的组合观看一个 n 部分系列的每一集，你必须至少观看 n! +(n – 1)! + (n – 2)! + n – 3 集——这是4chan用户的贡献——最多观看 n! +(n – 1)! + (n – 2)! + (n – 3)! + n – 3 集，我们通过Egan的工作知道这一点。
对于八集系列《万花筒 (Kaleidoscope)》来说，你至少需要观看46,085集，最多需要观看46,205集。对于有 14 集的《凉宫春日的忧郁 (The Melancholy of Haruhi Suzumiya)》，即《春日 (Haruhi)》，这个数字急剧增加：最少 93,884,313,611 集，最多 93,924,230,411 集。请记住，这不是一个完整的解决方案——它只是为superpermutation的大小设置了一个范围，这将使你能够以所有可能的顺序有效地观看该系列。
幸运的是，Egan还提供了一种构建相应superpermutation的算法。这使《春日 (Haruhi)》的粉丝能够计算出剧集的最佳观看顺序。但是，以平均每集 24 分钟的时长计算，观看这个superpermutation大约需要 400 万年。
Rights & Permissions Manon Bischoff 是 Spektrum（《科学美国人 (Scientific American)》的合作出版物）的理论物理学家和编辑。
用科学拓展你的世界
学习和分享塑造我们当今世界的最激动人心的发现、创新和想法。
SubscribeSign up for our newslettersSee the latest storiesRead the latest issueGive a Gift Subscription
Follow Us:
Scientific American is part of Springer Nature, which owns or has commercial relations with thousands of scientific publications (many of them can be found at www.springernature.com/us). Scientific American maintains a strict policy of editorial independence in reporting developments in science to our readers. © 2024 SCIENTIFIC AMERICAN, A DIVISION OF SPRINGER NATURE AMERICA, INC.ALL RIGHTS RESERVED.