今天听说了 Conway's Soldiers ，这是 Conway 大牛在 1961 年提出的一个数学谜题（似乎 Conway 的出镜率也太高了），我觉得非常有意思，在这里跟大家介绍一下。内容基本上来自于 Wikipedia 的相关页面。
假设有一个无限大的棋盘。棋盘上可以放置一些象征着士兵的棋子。一个棋子可以跳过并吃掉和它相邻的一枚棋子（就像孔明棋一样）。这是棋子的唯一一种移动方式。现在，在某个位置画一条无限长的水平线，你需要在水平线下面放置足够多的棋子，使得它们前仆后继地往水平线上方跳，最终能够跳到水平线以上 n 个单位的位置。
如图所示，当 n = 1 时，两个棋子就够了。当 n = 2 时，我们需要 4 个棋子。当 n = 3 时，最少需要 8 个棋子。
在一篇老日志中，我提到了一个经典的概率问题：平均需要抛掷多少次硬币，才会首次出现连续两个正面？它的答案是 6 次。它的计算方法大致如下。
首先，让我们来考虑这样一个问题： k 枚硬币摆成一排，其中每一枚硬币都可正可反；如果里面没有相邻的正面，则一共有多少种可能的情况？这可以用递推的思想来解决。不妨用 f(k) 来表示摆放 k 枚硬币的方案数。我们可以把这些方案分成两类：最后一枚硬币是反面，或者最后一枚硬币是正面。如果是前一种情形，则我们只需要看前 k - 1 枚硬币有多少摆法就可以了；如果是后一种情形，那么倒数第二枚硬币必须是反面，因而这种情形下的方案数就取决于前 k - 2 枚硬币的摆放方案数。因此我们得到， f(k) = f(k - 1) + f(k - 2) 。由于摆放一枚硬币有两种方案，摆放两枚硬币有三种方案，因而事实上 f(k) 就等于 Fk+2 ，其中 Fi 表示 Fibonacci 数列 1, 1, 2, 3, 5, 8, …的第 i 项。
而“抛掷第 k 次才出现连续两个正面”的意思就是，最后三枚硬币是反、正、正，并且前面 k - 3 枚硬币中正面都不相邻。因此，在所有 2k 种可能的硬币正反序列中，只有 Fk-1 个是满足要求的。也就是说，我们有 F1 / 4 的概率在第二次抛币就得到了连续两个正面，有 F2 / 8 的概率在第三次得到连续两个正面，有 F3 / 16 的概率在第四次得到连续两个正面⋯⋯因此，我们要求的期望值就等于：
这道题的答案有几个字母？答案：four。
有趣的是，这是唯一的答案。如果令函数 f(n) 表示非负整数 n 的英文表达中有多少个字母（不算空格和短横线）， n=4 是该函数的唯一不动点。
n 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …
f(n) 4, 3, 3, 5, 4, 4, 3, 5, 5, 4, 3, …
事实上， @IanMathmogician 发现了一个更有趣的“数学冷知识”：任取一个 0 到 100 之间的整数 n ，算出这个数的英文表达中的字符个数，再算出所得结果的英文表达的字符数，并这样一直迭代下去，最后总会得到数字 4 。我用 Mathematica 做了一张图片，可以让大家直观地看到，这真的可以说是条条大路通向数字 4 啊。
数学猜想并不总是对的，错误的数学猜想不占少数。关键在于，有时反例太大，找出反例实在是太困难了。这篇日志收集了很多“大反例”的例子，里面提到的规律看上去非常诱人，要试到相当大的数时才会出现第一个反例。
千万不要迷信规律
圆上有 n 个点，两两之间连线后，最多可以把整个圆分成多少块？
上图显示的就是 n 分别为 2 、 3 、 4 的情况。可以看到，圆分别被划分成了 2 块、 4 块、 8 块。规律似乎非常明显：圆周上每多一个点，划分出来的区域数就会翻一倍。
上帝创造了整数，其余的则是我们人类的事了。正因为如此，质数、完全数、Fibonacci 数之类的数列才会让数学家们如痴如醉，因为它们的存在是如此自然，没有任何人造的因素。事实上，数学家们对这些数的认识也越来越丰富，挖掘出了这些数列中越来越深刻的性质。
不过，人类确实太渺小了。还有好多构造异常简单的“纯天然数列”，我们了解得实在太少。Kolakoski 数列就是最好的例子之一。
Kolakoski 数列仅由 1 和 2 构成，其中头 100 个数是
1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1,
2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1,
1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2,
1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2,
2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, ...
最近在做网站测试时，遇到了需要在输入框输入 3000 字的测试用例。联想到平时聊天时经常复制粘贴一堆笑脸刷屏讨 MM 欢心的行为，不由想到了一个有趣的问题：为了输入一定数量的字符，最少需要按多少个键？
大家最常用的策略或许是， 先输一些字符，然后全选复制，粘贴到一定规模后，再全选复制，粘贴到一个新的数量级，如此反复。注意到进入全选状态（并且复制后），第一次粘贴将会覆盖掉选中的部分，第二次粘贴才会增加原来的文本长度。当然，全选复制后按一次向右键也可以消除选中状态，不过却并没有节省按键次数。因此我们规定，在输入字符时只有四种原子操作：
1. 按一个按键，输入一个字符
2. 按 Ctrl + A ，全选
3. 按 Ctrl + C ，复制
4. 按 Ctrl + V ，粘贴
在所有寻找数字规律的谜题中，下面这个难题可能是最有意思的题目之一了：
1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ⋯⋯
上面这个数列有什么规律？
若你是第一次听到这个问题，你一定会非常喜欢问题的答案：下一个数是对上一个数的描述，比方说 1211 里有 “ 1 个 1 ， 1 个 2 ， 2 个 1 ” ，那么 111221 就是它的下一个数。通常我们把这个数列叫做“外观数列”。
作为一个让人拍案叫绝的智力游戏，外观数列的故事似乎就已经到此为止了。可是，人们渐渐发现，外观数列里面还大有文章可做。例如，数列中的数虽然会越来越长，但数字 4 始终不会出现。这些优雅的性质成功地引来了数学家们的围观。在对外观数列的研究中，最引人注目的成果之一要归功于英国数学家 John Conway 。 1987 年， John Conway 发现，在这个数列中，相邻两数的长度之比越来越接近一个固定的数。最终，数列的长度增长率将稳定在 30% 左右。事实上，如果把数列中第 n 个数的长度记作 L_n ，则当 n 趋于无穷大的时候， L_(n+1) / L_n 将趋于一个极限。 John Conway 把这个极限用希腊字母 λ 表示，并证明了这个数是 71 次方程
x^71 - x^69 - 2*x^68 - x^67 + 2*x^66 + 2*x^65 + x^64 - x^63 - x^62 - x^61 - x^60 - x^59 + 2*x^58 + 5*x^57 + 3*x^56 - 2*x^55 - 10*x^54 - 3*x^53 - 2*x^52 + 6*x^51 + 6*x^50 + x^49 + 9*x^48 - 3*x^47 - 7*x^46 - 8*x^45 - 8*x^44 + 10*x^43 + 6*x^42 + 8*x^41 - 5*x^40 - 12*x^39 + 7*x^38 - 7*x^37 + 7*x^36 + x^35 - 3*x^34 + 10*x^33 + x^32 - 6*x^31 - 2*x^30 - 10*x^29 - 3*x^28 + 2*x^27 + 9*x^26 - 3*x^25 + 14*x^24 - 8*x^23 - 7*x^21 + 9*x^20 + 3*x^19 - 4*x^18 - 10*x^17 - 7*x^16 + 12*x^15 + 7*x^14 + 2*x^13 - 12*x^12 - 4*x^11 - 2*x^10 + 5*x^9 + x^7 - 7*x^6 + 7*x^5 - 4*x^4 + 12*x^3 - 6*x^2 + 3*x - 6 = 0
的唯一实数解，它约为 1.303577 。这就是传说中的 Conway 常数。
心电图数列 (EKG Sequence) 的定义简单而有趣：第一项为 1 ，第二项为 2 ，以后的每一项都是最小的和前一项不互质并且不曾出现过的数。换句话说，数列 a(1)=1 ， a(2)=2 ，且当 n>2 时取 a(n) 为所有满足以下两个条件的数中最小的那一个：该数与 a(n-1) 有大于 1 的公约数，并且该数与前面 n-1 项都不相等。心电图数列的前面 20 项为
1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16, 20, 22, 11 ...
为什么它叫做心电图数列呢？原因很简单——因为把它描绘在图象上时，看上去像一张心电图。
Matrix67 |
2011-09-11 22:53 | 
