细侃那些悬而未决的数学趣味谜题
发布时间：2011-02-26 14:20
十个悬而未决的数学趣味谜题
译者:July 二零一一年二月二十六日
参考文献：Mathematical Puzzles，by Peter Winkler。
此书豆瓣读书地址：book.douban/subject/2483910/
----------------------------------------
我之前曾在我的博客里阐述过，世界七大数学难题与Hilbert的23个问题，不少读者反映强烈，一方面纠结于此些问题解决或证明的难度之大，同时，又不得不叹服，数学之美与其无穷魅力。
和Goldbach 猜想、Riemann假设等经典数学难题不同，有些悬而未解的数学问题也很难解决，但同时，却趣味性很强。
这些问题，“数学性”比较弱，乍看上去并没有触及深刻的数学理论，似乎是一道可以被瞬间秒杀的数学趣题，让数学爱好者们“不到一个巧解就不爽”；但令人称奇的是，它们的困难程度却不亚于那些著名的数学猜想，这或许比各个领域中艰深的数学难题更折磨人。
本文，从Mathematical Puzzles，一书中，节选了10个悬而未决的数学趣味谜题，以飨读者。同时，本文也参考了网友Matrix67的博客：www.matrix67/blog/。在此表示感谢。同时，本人暂时无法了解到这些问题的解决或证明情况的最新进展，所以，有不正之处，还望各位读者批评指正。谢谢。
ok，闲不多说，咱们开始，一有空，就多多思考下吧。
一、3x + 1问题
问题描述：从任意一个正整数开始，重复对其进行下面的操作：
如果这个数是偶数，把它除以 2 ；如果这个数是奇数，则把它扩大到原来的 3 倍后再加1 。
问：序列是否最终总会变成 4, 2, 1, 4, 2, 1, … 的循环？
乍看之下，问题非常简单，突破口很多，于是数学家们纷纷往里面跳；殊不知进去容易出
去难，不少数学家到死都没把这个问题搞出来。已经中招的数学家不计其数。
3x + 1 问题又叫 Collatz 猜想、 Syracuse 问题、 Kakutani 问题、 Hasse 算法、 Ulam 问题等等。后来，由于命名争议太大，直接叫做 3x + 1 问题算了。
举一个例子，来说明数列收敛有多么没规律。如从 26 开始算起，10 步就掉入了“421 陷
阱”：
26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, …
怎么样，明白了此问题了吧，ok，再举一个例子，从27开始算起：此时，数字会一路飙升到几千多，你很可能会一度认为它脱离了“421 陷阱”；但是，经过上百步运算后，它还是跌了回来：
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, 719, 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, …
July附注：这样，我想你已经完全明白了此问题的描述，怎么样，有什么想法，或意见，留言告诉我吧。期待你的贡献。:D。

二、随机01串的最长公共子序列steele
问题描述：如果从数字序列 A 中删除一些数字就能得到数字序列 B ，我们就说 B 是 A 的子序列。例如， 110 是 010010 的子序列，但不是 001011 的子序列。两个序列的“公共子序列”有很多，其中最长的那个就叫做“最长公共子序列”。
随机产生两个长度为 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 证明了 0.773911 < C1/2 < 0.837623 ，看上去 Michael Steele 的猜想似乎很可能是对的。 2003 年， George Lueker 证明了 0.7880 < C1/2 < 0.8263 ，推翻了 Michael Steele 的猜想。
更糟的是，“当 p 为 1/2 时 Cp 达到最小”似乎是一件很靠谱的事，但这个结论也无人能证明。
July附注：关于最长公共子序列问题，本博客，有所初步阐述。但鉴于那篇文章，阐述的
不是特别理想、透彻，这里，就不贴出来献丑了。

三、排序问题加强版
问题描述：
有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 步之内完成排序：
55, 44, 33, 22, 11
54, 54, 33, 22, 11
54, 43, 53, 22, 11
54, 43, 32, 52, 11
54, 43, 32, 21, 51
54, 43, 21, 32, 51
54, 31, 42, 32, 51
41, 53, 42, 32, 51
41, 32, 54, 32, 51
41, 32, 42, 53, 51
41, 32, 42, 31, 55
41, 32, 21, 43, 55
41, 21, 32, 43, 55
11, 42, 32, 43, 55
11, 22, 43, 43, 55
11, 22, 33, 44, 55
第一次看上去似乎很不可思议，但细想一下还是能想明白的：
同一个盒子里能够放两个数，确实多了很多新的可能。如果左边盒子里的某个数比右边某个盒子里的数大，我们就说这两个数构成一个逆序对；但如果两个不同的数在同一个盒子里，我们就把它们视作半个逆序对。
现在让我们来看看，一次交换最多能消除多少个逆序对。假设某一步交换把 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 步交换是不行的。于是，这个问题又变成了一个诱人的坑，至今仍未被填上。

July附注：排序问题，历来是这个世界上应用最广泛同时也是比较难的一类问题。目前，
本Blog内正在一步一步阐述基本的八大排序算法，欢迎阅读。
四、环形跑道难题
问题描述：
有一个环形跑道，总长为 1 个单位。n 个人从跑道上的同一位置出发，沿着跑道顺时针一直跑下去。每个人的速度都是固定的，但不同人的速度不同。证明或推翻，对于每一个人，总会有一个时刻，他与其他所有人的距离都大于 1/n 。
乍看上去，这个问题无异于其它各种非常巧妙的初等组合数学问题，但不可思议的是，这个问题竟然直到现在仍没解决。目前最好的结果是，当 n ≤ 6 时，结论是成立的。直觉上，对于更大的 n ，结论也应该成立，不过尚未有人证明。

五、天使和恶魔
问题描述：
天使和恶魔在一个无限大的棋盘上玩游戏。每一次，恶魔可以挖掉棋盘上的任意一个格子，天使则可以在棋盘上飞行 1000 步之后落地；如果天使落在了一个被挖掉的格子上，天使就输了。
问：恶魔能否困住天使（在天使周围挖一圈厚度 1000 的坑）？
这是John Conway的一个经典谜题。作为一个很“正常”的组合游戏，天使与恶魔的问题竟然一直没能得到解决。目前已经有的结论是，如果天使每次只能移动一步，恶魔一定能获胜。不过，天使只要能每次飞两步，似乎就已经很无敌了。当然，魔鬼的优势也不小——它不用担心自己“走错”，每多挖一个坑对于它来说都是有利的。
话说回来，Conway本人似乎仍然相信天使能赢——他悬赏了 1000 美元征求恶魔必胜的证明，但只悬赏了 100 美元征求天使必胜的证明。
July附注: 听说这个问题，已经解决了。解决情况是：n ≥ 2 时天使贏。 详情参见这里：/~oddvark/angel/。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。