写一个“宅男拯救世界”的故事。
我们先寻找一个最短的序列，可以包含
的所有排列。
的所有排列有下面六种：
可以看到，
包含了以上所有的排列作为子列，并且不难验证，他是长度最短的拥有这个性质的序列。
我们现在考虑对
这个序列问同样的问题，长度最短，并且包含所有
的各种排列的序列有多长呢？数学家把这种序列叫做“超排列”。如果我们仔细思考几分钟，不难发现一种很自然的归纳的构造方法：假设
个元素的超排列长度是
，我们可以把这个序列“分拆”成若干个长度为
的子列，然后在其中“插入”第
个元素，我们可以得到一个新序列，包含
个元素的所有排列，而且长度只有
。具体操作如下图：
并且，数学家们已经验证，一个元素的超排列长度为
，两个元素超排列长度为
，三个元素超排列长度为
，四个元素的超排列长度为
，以及五个元素的超排列长度为
。
通过我们刚才的归纳构造，我们已经构造出包含
个元素所有排列的长度为
的序列了。我们暂且不叫这个序列为“超排列”，主要是出于数学家的严谨，因为我们还没有证明这个序列的长度最短。但是我们可以做一个很合理的猜想：
猜想：
包含个元素的超排列的长度为
我们也可以去尝试证明这个猜想。由于我们已经有了这个长度的构造，我们只需要再证明下界：
个元素的超排列至少是这个长度。
不难看出，
个元素的超排列的长度至少是
：在序列中我们先任意放置一个排列，然后对每个剩余的
种排列，我们至少需要一个元素的固定它。如果我们稍微努力一下去改进这个方法，我们可以证明超排列长度至少是
，因为不难发现，用一个元素去确定一个排列是不够的。甚至，如果我们再去改进一下这个方法，我们可以证明超排列长度至少是
。
看起来胜利在望！感觉只要我们花足够多的时间，足够努力去打磨这个方法，我们最终总能证明，超排列的长度至少是
，从而证明这个猜想。事实上，当时每一个了解这个问题的数学家，都确信猜想成立。当时有人在 MathOverFlow 上问这个问题，回答者们甚至都开始讨论起输出超排列的序列的算法了。这个问题甚至还出现在了 1998 年的土耳其信息学竞赛里。看起来计算机学家们已经默认我们构造出的序列就是超排列了，他们开始关心如何更快的输出这个序列了。当时很多数学家都在怀疑，这个猜想到底是不是真正的“未解决的数学问题”，还是只是大家懒得去花时间写下这个人人都认为成立并且简单的证明。
然而。。这个猜想是错的。2014 年，Houston 证明了这个猜想在所有
的情形下都是错的。目前最新的上界是，包含
个元素的超排列长度至多是
你可能以为我跑题了，这里根本就没有宅男什么事嘛。下面讲一下这个故事的另一条线。有一个网络论坛，叫 4chan，主要讨论动漫，二次元的一个论坛，看起来是一个宅男很喜欢去的地方。
另外，有一个日本动漫叫《凉宫春日的忧郁》，一共 14 集。这个漫画大概由于情节比较跳跃，每集之间的关联不是很大，甚至首播和重播的剧集播放顺序都各自不同。于是在 4chan 上有人问，如果我想看到这个动漫所有可能的播放顺序，我至少要连续看多少集？这个问题实际上是在问，包含
个元素的超排列，长度有多长。
一个小时之内，就有匿名网友给出了这个问题的一个下界。他说，他不清楚确切需要看多少集，但是他能证明，至少需要看多少集。他在下面的回复包含了完整的证明，给出了目前最好的下界：
。
由于当时数学家们确信之前提到的猜想是正确的，因此这个匿名同学的回复并没有引起重视。毕竟当你已经确切知道一个值是多少了，你就对这个值最少是多少这件事不感兴趣了。直到 Houston 证明了这个猜想是错误的之后，4chan 上的证明才重新得到关注。并且这个下界和我们现在有的最好的上界惊人的接近。
后来，Houston 和合作者写了篇 paper，把这个 4chan 的匿名同学放到了第一作者。。
参考资料
文中图片以及部分信息来自 wiki 和 N. Johnston 教授的博客。
微信扫一扫 
