243最伟大的数学家(2/2)

编号为n的小球，第2个盒子里放两个编号为n-1的小球，以此类推，第n个盒子里放两个编号为1的小球。每一次，你可以在相邻两个盒子中各取一个小球，交换它们的位置。为了把所有小球放进正确的盒子里，最少需要几次交换？

为了说明这个问题背后的陷阱，我们不妨先拿n=5的情况做个例子。首先，如果每个盒子里只有一个球，问题就变成了经典的排序问题了：只能交换相邻元素，如何最快地把5，4，3，2，1变成1，2，3，4，5？如果一个数列中前面的某个数反而比后面的某个数大，我们就说这两个数是一个“逆序对”。显然，初始情况下所有数对都是逆序对，n=5时逆序对共有10个。我们的目的就是要把这个数目减少到0。而交换两个相邻的数只能消除一个逆序对，因此10次交换是必需的。

不过，题目里面每个盒子里有两个球，那么是不是必须要交换20次才行呢？错！下面这种做法可以奇迹般地在15步之内完成排序：

……。

第一次看上去似乎很不可思议，但细想一下还是能想明白的：同一个盒子里能够放两个数，确实多了很多新的可能。如果左边盒子里的某个数比右边某个盒子里的数大，我们就说这两个数构成一个逆序对；但如果两个不同的数在同一个盒子里，我们就把它们视作半个逆序对。现在让我们来看看，一次交换最多能消除多少个逆序对。假设某一步交换把ab，cd变成了ac，bd，最好的情况就是bc这个逆序对彻底消除了，同时ac、bd两个逆序对消除了一半，ab、cd两个（已经消除了一半的）逆序对也消除了一半，因此一次交换最多可以消除3个逆序对。由于一开始每个盒子里的两个相同的数都会在中间的某个时刻分开来，最后又会合并在一起，因此我们可以把初始时两个相同的数也当作一个逆序对。这样的话，初始时每两个数都是逆序对，n个盒子里将产生c(2n，2)个逆序对。自然，我们至少需要c(2n，2)/3步才能完成排序。当n=5时，c(2n，2)/3=15，这就说明了上面给出的n=5的排序方案是最优的。

这个分析太巧妙了，实在是让人拍案叫绝。就只可惜，这个下界并不是总能达到的。当n=6时，上述分析得出的下界是22步，但计算机穷举发现没有23步交换是不行的。于是，这个问题又变成了一个诱人的坑，至今仍未被填上。

刘卷第六个问题是tkle猜想：

如果一个图中，每条边都与其它所有边相交恰好一次（顶点处相接也算相交），这个图就叫做一个tkle。问，是否存在边数大于顶点数的tkle图？

【目前已知的最好的结果是，一个tkle的边数不会超过顶点数的两倍减3。】

曾教授抹去泪水，说道：“好了，孩子，你回去吧，这些数学题你慢慢的去解。”

刘卷不知道曾教授为什么那样激动，他收拾好东西，说道：“曾教授，那我回去了。”

曾教授看着刘卷渐渐远去的背影，不由说道：“我们中国又将出现一位最伟大的数学家了。”