243最伟大的数学家（2 / 2）
随机产生两个长度为 n 的 01 序列，其中数字 1 出现的概率是 p ，数字 0 出现的概率是 1 - p 。用 cp(n) 来表示它们的最长公共子序列的长度，用 cp 来表示 cp(n) / n 的极限值。
关于 cp 的存在性，有一个非常巧妙的证明；然而，这个证明仅仅说明了 cp 的存在性，它完全没有给计算 cp 带来任何有用的提示。
即使是 c1/2 的值，也没人能成功算出来。 michael steele 猜想 c1/2 = 2/(1 + √2) ≈ 0。828427 。后来， v。 chvátal 和 d。 sankoff 证明了 ……，看上去 michael steele 的猜想似乎很可能是对的。 2003 年， george lueker 证明了 0。7880 lt; c1/2 lt; 0。8263 ，推翻了 michael steele 的猜想。
更糟的是，“当 p 为 1/2 时 cp 达到最小”似乎是一件很靠谱的事，但这个结论也无人能证明。
刘卷第三个问题是：曲线的内接正方形
证明或推翻，在平面中的任意一条简单封闭曲线上，总能找到四个点，它们恰能组成一个正方形。
这样一个看上去如此基本的问题，竟然没有被解决！这个 blog 上曾经证明过，任意凸多边形上总存在四个可以构成正方形的点；对证明方法进行改进，可以把结论扩展到凹多边形上。目前，对于充分光滑的曲线，似乎已经有了肯定的结论；但对于任意曲线来说，这仍然是一个悬而未解的问题。平面上的曲线无奇不有，说不准我们真能精心构造出一种不满足要求的怪异曲线。
刘卷的第四个问题是：环形跑道难题
有一个环形跑道，总长为 1 个单位。n 个人从跑道上的同一位置出发，沿着跑道顺时针一直跑下去。每个人的速度都是固定的，但不同人的速度不同。证明或推翻，对于每一个人，总会有一个时刻，他与其他所有人的距离都大于 1/n 。
乍看上去，这个问题无异于其它各种非常巧妙的初等组合数学问题，但不可思议的是，这个问题竟然直到现在仍没解决。目前最好的结果是，当 n ≤ 6 时，结论是成立的。直觉上，对于更大的 n ，结论也应该成立，不过尚未有人证明。
刘卷的第五个问题是：排序问题加强版
有 n 个盒子，从左至右依次编号为 1， 2， …， n 。第 1 个盒子里放两个编号为 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 步交换是不行的。于是，这个问题又变成了一个诱人的坑，至今仍未被填上。
刘卷第六个问题是 thrackle 猜想：
如果一个图中，每条边都与其它所有边相交恰好一次（顶点处相接也算相交），这个图就叫做一个 thrackle 。问，是否存在边数大于顶点数的 thrackle 图？
【目前已知的最好的结果是，一个 thrackle 的边数不会超过顶点数的两倍减 3 。】
曾教授抹去泪水，说道：“好了，孩子，你回去吧，这些数学题你慢慢的去解。”
刘卷不知道曾教授为什么那样激动，他收拾好东西，说道：“曾教授，那我回去了。”
曾教授看着刘卷渐渐远去的背影，不由说道：“我们中国又将出现一位最伟大的数学家了。”