在4Chan讨论如何播放《凉宫春日》动画匿名网民为组合数学难题带来进展

导读 改编自作家谷川流轻小说作品的动画《凉宫春日的忧郁》2006年版总共有14集,首次播出时电视台播放顺序并未循从故事发展时序。到了2009年

改编自作家谷川流轻小说作品的动画《凉宫春日的忧郁》2006年版总共有14集,首次播出时电视台播放顺序并未循从故事发展时序。到了2009年,动画再次播放,但按故事发生时序播出,并在中途加入新作品。由于2006年版本的播放顺序跟故事发生的时序有别,网络上有不少关于应以甚么顺序看这套动画的讨论。

2011年,有人在贴图讨论版网站4Chan的科学及数学版(/sci/)上提出「凉宫春日问题」︰如果要把《凉宫春日的忧郁》(2006年版,下同)所有可能的播放次序都看一遍,最少要看多集?

排序问题

一般来说,如果动画有n集的话,可能的排序就会有 1 × 2 × 3 ×… × n 个,这数字称为n的阶乘(factorial),记作「n!」。随着n越来越大,n!会急剧增长,14集的动画总共有14!个可能次序,即有87,178,291,200——即近872亿——种可能。

14集实在太多,让我们先从简单的例子开始。假设动画只有两集,播放排序仅得两个可能,我们可以先顺次序看,然后再倒转看——以数字代表集数的话如下︰1, 2, 2, 1。如果我们只在意排序,就不必重複看第二集两次,以「1, 2, 1」的方式看三集便能达成目标。

假设动画有三集,则有6个可能的播放次序︰

1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1

如果以「1, 2, 3, 1, 2, 1, 3, 2, 1」的次序观看,便可以把上述6个可能排序都看了一遍。

数学上每一个可能的次序称为「排列」(permutation),直观地理解,就是把n件东西不重複又没有遗漏地排队(为方便起见,我们可以把这n件东西以数字代表)。

至于上述的「凉宫春日问题」则讨论另一个相关概念,称为「超排列」(superpermutation)。对于任何数字n,「n-超排列」就是一个数列,当中包含了n件东西的所有排列。这样说好像很抽象,不过我们其实已在上文见过︰「1, 2, 1」就是一个「2-超排列」;「1, 2, 3, 1, 2, 1, 3, 2, 1」就是一个「3-超排列」。

最小超排列问题

换言之,只要跟着一个「14-超排列」去播放《凉宫春日的忧郁》,你就能够以所有可能的次序去看完这套动画——前提是你有足够时间。而「凉宫春日问题」的重点在于以「最少的集数」去看完,用数学家的语言来说,就是要找到一个「最小超排列」(minimal superpermutation)。

早在1993年,已有数学家提出寻找最小超排列的问题。对于较小的数字,数学家已经找到其最小超排列。假如总共有5集动画,按以下次序播放153集便能够看完所有可能排序︰

1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 1, 2, 5, 3, 4, 1, 2, 3, 5, 4, 1, 2, 3, 1, 4, 5, 2, 3, 1, 4, 2, 5, 3, 1, 4, 2, 3, 5, 1, 4, 2, 3, 1, 5, 4, 2, 3, 1, 2, 4, 5, 3, 1, 2, 4, 3, 5, 1, 2, 4, 3, 1, 5, 2, 4, 3, 1, 2, 5, 4, 3, 1, 2, 1, 3, 4, 5, 2, 1, 3, 4, 2, 5, 1, 3, 4, 2, 1, 5, 3, 4, 2, 1, 3, 5, 4, 2, 1, 3, 2, 4, 5, 1, 3, 2, 4, 1, 5, 3, 2, 4, 1, 3, 5, 2, 4, 1, 3, 2, 5, 4, 1, 3, 2, 1, 4, 5, 3, 2, 1, 4, 3, 5, 2, 1, 4, 3, 2, 5, 1, 4, 3, 2, 1, 5, 4, 3, 2, 1

要到2014年,才有人证明不存在长度小于153的「5-超排列」。过往有数学家猜想,最小的「n-超排列」长度为 1! + 2! + 3! + ... + n!。当n等于5或以下时,这个猜想成立,不过数学家候斯顿(Robin Houston)在2014年找到了一个长度为872的「6-超排列」,比起猜想的长度873短。即使如此,他也不确定自己找到的是最小超排列。

在上个星期五,科幻小说家伊根(Greg Egan)在Twitter表示他根据数学家威廉斯(Aaron Williams)一篇论文预印本,修改其方法后找到一个产生超排列的演算法。伊根指他的演算法所产生的最小「n-超排列」长度为 n! + (n-1)! + (n-2)! + (n-3)! + (n-3),当n大于6的时候,长度就会小于猜想的数字,他更写了一个程式,得出7-/8-/9-超排列。

利用伊根的公式计算——假设他的方法正确——如果要看完14集凉宫春日动画的各种顺序,「只需要」看93,924,230,411集就行。伊根的演算法为最小超排列找到长度上限,那么下限是多少呢?

来自4Chan的证明

上星期二侯斯顿发现,在一个讨论「凉宫春日问题」的网站上,有条公式计算最小超排列的长度下限,而这条公式是已知的最佳结果。网站的内容正好来自2011年4Chan上的讨论。

根据备份网站的记录,一位化名「Lower bounds」(下限)的网民在「凉宫春日问题」的讨论串中表示︰「我想我证明了下限是 n! + (n-1)! + (n-2)! + (n-3)」,用五则帖文的篇幅提供证明,并请其他网民检查有没有漏洞。

候斯顿跟伊根讨论后,认为这位「Lower bounds」的证明应该成立,然而他指出,因为这个证明不属于学术文献的一部分,其他数学家或会犹豫要不要相信及引用,所以这个证明现在处于一个奇怪的状态。数学家彭通(Jay Pantone)则把证明以数学论文的形式重写,以便其他数学家阅读。

虽然证明者身分未明,但匿名并不影响证明是否成立。彭通说︰「数学美丽之处,在于证明从假设出发,得出结论,你必须说服怀疑的读者你的证明正确,而这不需要他们得悉你的身分。」

伊顿以及这位4Chan网民的贡献,让我们知道「凉宫春日问题」的答案介乎93,884,313,611及93,924,230,411之间——即大约播放939亿集,便能看完《凉宫春日的忧郁》的所有可能排序。候斯顿、彭通及其他数学家现正努力结合两人的证明,希望得出能够準确计算出最小超排列长度的公式。

相关文章︰

网络讨论提供协助 数学家陶哲轩破解80年难题 业余数学家协助解答的难题︰怎样用五边形来密铺平面? 没有人明白的数学证明能否成立?

资料来源︰

An anonymous 4chan post could help solve a 25-year-old math mystery (The Verge) Greg Egan’s Twitter Superpermutations by Greg Egan Robin Houston's Twitter Superpermutations: lower bound (Robin Houston's Blog) Permutations Thread III (/sci/ - Science & Math) (Backup) The Haruhi Problem (/sci/ - Math & Science Wiki) “Obvious” Does Not Imply “True”: The Minimal Superpermutation Conjecture is False (Nathaniel Johnston’s blog) All Minimal Superpermutations on Five Symbols Have Been Found (Nathaniel Johnston's Blog) Tackling the Minimal Superpermutation Problem (Robin Houston 2014, Preprint) Jay Pantone, A lower bound on the length of the shortest superpattern (PDF)

免责声明:本文由用户上传,如有侵权请联系删除!

猜你喜欢

最新文章