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 个,这也就
Copyright © 2018-2021 Wenke99.com All rights reserved
工信部备案号:浙ICP备20026746号-2
公安局备案号:浙公网安备33038302330469号
本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。