1、天使和恶魔天使和恶魔在一个无限大的棋盘上玩游戏。每一次，恶魔可以挖掉棋盘上的任意一个格子，天使则可以在棋盘上飞行 1000 步之后落地；如果天使落在了一个被挖掉的格子上，天使就输了。问题：恶魔能否困住天使（在天使周围挖一圈厚度 1000 的坑）？这是 Conway 大牛的又一个经典谜题。经常阅读这个 Blog 的人会发现， Conway 大牛的出镜率极高。不过这一次， Conway 真的是伤透了不少数学家的脑筋。作为一个很“正常 “的组合游戏，天使与恶魔的问题竟然一直没能得到解决。目前已经有的结论是，如果天使每次只能移动一步，恶魔一定能获胜。不过，天使只要能每次飞两步，似乎就已经很无敌了。当然
2、，魔鬼的优势也不小它不用担心自己“走错“，每多挖一个坑对于它来说都是有利的。话说回来， Conway 本人似乎仍然相信天使能赢 他悬赏了 1000 美元征求恶魔必胜的证明，但只悬赏了 100 美元征求天使必胜的证明。Gilbreath 猜想从小到大依次列出所有的质数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, .求出相邻两项之差：1, 2, 2, 4, 2, 4, 2, 4, 6, 2, .现在，再次求出所得序列中相邻两项之差，又会得到一个新的序列：1, 0, 2, 2, 2, 2, 2, 2, 4, .重复对所得序列进行这样的操作，我们还可以依次得到1,
3、2, 0, 0, 0, 0, 0, 2, .1, 2, 0, 0, 0, 0, 2, .1, 2, 0, 0, 0, 2, .1, 2, 0, 0, 2, .大家会发现一个有趣的规律：每行序列的第一个数都是 1。某日，数学家 Norman L. Gilbreath 闲得无聊，在餐巾上不断对质数序列求差，于是发现了上面这个规律。Gilbreath 的两个学生对前 64 419 行序列进行了检验，发现这个规律始终成立。1958 年，Gilbreath 在一个数学交流会上提出了他的发现， Gilbreath 猜想由此诞生。这个规律如此之强，很少有人认为猜想不成立。1993 年，Andrew Odly
4、zko 对 10 000 000 000 000 以内的质数（也就是 346 065 536 839 行）进行了检验，也没有发现反例。不过，这一看似简单的问题，几十年来硬是没人解决。3x + 1 问题从任意一个正整数开始，重复对其进行下面的操作：如果这个数是偶数，把它除以 2 ；如果这个数是奇数，则把它扩大到原来的 3 倍后再加 1 。序列是否最终总会变成 4, 2, 1, 4, 2, 1, 的循环？这个问题可以说是一个“坑 “乍看之下，问题非常简单，突破口很多，于是数学家们纷纷往里面跳；殊不知进去容易出去难，不少数学家到死都没把这个问题搞出来。已经中招的数学家不计其数，这可以从 3x + 1
5、 问题的各种别名看出来： 3x + 1 问题又叫 Collatz 猜想、 Syracuse 问题、 Kakutani 问题、Hasse 算法、 Ulam 问题等等。后来，由于命名争议太大，干脆让谁都不沾光，直接叫做 3x + 1 问题算了。3x + 1 问题不是一般的困难。这里举一个例子来说明数列收敛有多么没规律。从 26 开始算起， 10 步就掉入了“421 陷阱“：26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 但是，从 27 开始算起，数字会一路飙升到几千多，你很可能会一度认为它脱离了“421 陷阱“；但是，经过上百步运算后，它还是跌了回来
6、：27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 71
7、9, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 随机 01 串的最长公共子序列如果从数字序列 A 中删除一些数字就能
8、得到数字序列 B ，我们就说 B 是 A 的子序列。例如， 110 是 010010 的子序列，但不是 001011 的子序列。两个序列的“ 公共子序列 “有很多，其中最长的那个就叫做“最长公共子序列“。随机产生两个长度为 n 的 01 序列，其中数字 1 出现的概率是 p ，数字 0 出现的概率是 1 - p 。用 Cp(n) 来表示它们的最长公共子序列的长度，用 Cp 来表示 Cp(n) / n 的极限值。关于 Cp 的存在性，有一个非常巧妙的证明；然而，这个证明仅仅说明了 Cp 的存在性，它完全没有给计算 Cp 带来任何有用的提示。即使是 C1/2 的值，也没人能成功算出来。 Micha
9、el Steele 猜想 C1/2 = 2/(1 + 2) 0.828427 。后来， V. Chvtal 和 D. sankoff 证明了 0.773911 8 的情况究竟是否有解，目前尚无定论。(3/2)n 的小数部分假如 n 是正整数， (3/2)n 的小数部分在 0, 1 区间内稠密吗？ 目前，我们已经知道，对于任意无理数 a ， n a 的小数部分一定在 0, 1 区间内稠密。我们也已经知道，对于几乎所有的 t ，t (3/2)n 的小数部分在 0, 1 区间内稠密。我们还知道，对于几乎所有的实数 b 1 ， bn 的小数部分在 0, 1 区间内稠密。不过，这都还不足以解决我们刚刚提
10、到的问题。Singmaster 猜想在杨辉三角中，数字 1 出现了无穷多次。除了数字 1 以外，哪个数字出现的次数最多呢？6 出现了 3 次，不过不算多。 10 出现了 4 次，不过也不算多。 120 出现了 6 次，算多了吧？还不算多。目前已知的出现次数最多的数是 3003 ，它同时等于 C(3003, 1) 、 C(78, 2) 、 C(15, 5) 、 C(14, 6) ，在杨辉三角中出现了 8 次。有没有出现次数更多的数，目前仍然是一个未解之谜。真正精彩的来了。如果把正整数 a 在杨辉三角中出现的次数记作 N(a) ，那么函数 N(a) 是什么级别上涨的呢？ 1971 年，David
11、Singmaster 证明了 N(a) = O(log a) ，即 N(a) 最多是对数级别上涨的。他同时猜想 N(a) = O(1) ，即 N(a) 有一个上限。这也就是 Singmaster 猜想。由于我们一直没能找到出现次数超过 8 次的数，因而这个上界很可能就是 8 。不过， Singmaster 猜测这个上界更可能是 10 或者 12 。Erds 认为， Singmaster 的猜想很可能是正确的，但证明起来会非常困难。目前最好的结果是，N(a) = O(log a log log log a) / (log log a)3) 。重构猜想这可以说是图论中最重要的猜想之一，然而我却是最
12、近才听说。这个猜想叫做“重构猜想”（reconstruction conjecture），最早是由 Kelly 和 Ulam 提出的。它的叙述非常简单：对于某个顶点数为 n 的图（n 3），如果已知它的每一个顶点为 n - 1 的子图，是否足以将原图重构出来？让我们把这个问题变得形式化一些。假设 A 是一个至少有三个顶点的图（顶点无标号），把它的顶点数记作 n 。我们把去掉其中一个顶点后可能得到的所有 n 个子图所组成的多重集（允许重复元素的集合）叫做图 A 的 n - 1 子图集。重构猜想就是问，如果 A 、 B 两个图拥有完全相同的 n - 1 子图集，那么这两个图是否也一定同构？目前已经
13、发现，有很多类型的图都是可以重构的，比如完全图（显然）、不连通图、树等等。所有图都是可重构的吗？这是图论中最大的谜题之一。和其他的数学猜想不一样，如果要用计算机来检验这个猜想，其计算量相当惊人。目前，计算机仅仅验证了 n 11 的情况。Kusner 猜想定义 n 维空间中 P(p1, p2, , pn) 和 Q(q1, q2, , qn) 两点之间的 Manhattan 距离为 |p1 - q1| + |p2 - q2| + + |pn - qn| ，直观地说就是在 n 维网格中从 P 到 Q 的最短路径长度。某日，木遥告诉了我一个与此相关的数学未解之谜：在 n 维空间中，最多可以有多少个 Manhattan 距离两两相等的点？容易看出，这样的点至少可以有 2n 个，例如三维空间中 (1, 0, 0) 、 (-1, 0, 0) 、 (0, 1, 0) 、 (0, -1, 0) 、 (0, 0, 1) 、 (0, 0, -1) 就是满足要求的 6 个点。大家肯定会想，这应该就是点数最少的方案了吧？不过，真要证明起来可没那么容易。1983 年，Robert Kusner 猜想， n 维空间中 Manhattan 距离两两相等的点最多也只能有 2n 个，这也就
