经典证明:Conway的士兵

    今天听说了 Conway’s Soldiers ,这是 Conway 大牛在 1961 年提出的一个数学谜题(似乎 Conway 的出镜率也太高了),我觉得非常有意思,在这里跟大家介绍一下。内容基本上来自于 Wikipedia 的相关页面。     假设有一个无限大的棋盘。棋盘上可以放置一些象征着士兵的棋子。一个棋子可以跳过并吃掉和它相邻的一枚棋子(就像孔明棋一样)。这是棋子的唯一一种移动方式。现在,在某个位置画一条无限长的水平线,你需要在水平线下面放置足够多的棋子,使得它们前仆后继地往水平线上方跳,最终能够跳到水平线以上 n 个单位的位置。            如图所示,当 n = 1 时,两个棋子就够了。当 n = 2 时,我们需要 4 个棋子。当 n = 3 时,最少需要 8 个棋子。

比Conway生命游戏更酷的Langton蚂蚁

不知道有多少人已经熟知 Conway 的生命游戏,但却从没听说过 Langton 的蚂蚁游戏?反正我是其中之一。直到今天我才听说了这个比生命游戏更酷的游戏—— Langton 的蚂蚁。这也是一个二维自动机形式的零玩家游戏,不过我觉得它比生命游戏有趣得多。这有两个理由: 1. 它的算法过程更简单。初始时,蚂蚁位于一张空白画布的某个方格里。如果当前蚂蚁在白色方格上,则对当前方格反色,左转 90 度,前进一格;如果当前蚂蚁在黑色方格上,则对当前方格反色,右转 90 度,前进一格。如此反复。   

Conway常数是怎么得来的?

    在所有寻找数字规律的谜题中,下面这个难题可能是最有意思的题目之一了: 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 […]

实数、超实数和博弈游戏:数学的结构之美

(一)一个博弈游戏 让我们来玩一个游戏。下面有五行石子,白色的石子都是我的,黑色的石子都是你的。我们轮流拿走一个自己的石子,并且规定如果一个石子被拿走了,它后面的所有石子都要被扔掉。谁先没有拿的了,谁就输了。 ○●●○●●○●●○ ●○○●○●●○● ○○○○ ●●●○●●● ●

Penney 的游戏:正所谓后发制人,先发制于人

让我们来玩一个游戏。连续抛掷硬币,直到最近三次硬币抛掷结果是“正反反”或者“反反正”。如果是前者,那么我获胜,你需要给我 1 元钱;如果是后者,那么你获胜,我会给你 1 元钱。你愿意跟我玩这样的游戏吗?换句话说,这个游戏是公平的吗? 乍看上去,你似乎没有什么不同意这种玩法的理由,毕竟“正反反”和“反反正”的概率是均等的。连续抛掷三次硬币可以产生 8 种不同的结果,上述两种各占其中的 1/8 。况且,序列“正反反”和“反反正”看上去又是如此对称,获胜概率怎么看怎么一样。 实际情况究竟如何呢?实际情况是,这个游戏并不是公平的——我的获胜概率是你的 3 倍!虽然“正反反”和“反反正”在一串随机硬币正反序列中出现的频率理论上是相同的,但别忘了这两个序列之间有一个竞争的关系,它们要比赛看谁先出现。一旦抛掷硬币产生出了其中一种序列,游戏即宣告结束。这样一来,你就会处于一个非常窘迫的位置:不管什么时候,只要掷出了一个正面,如果你还没赢的话,你就赢不了了——在出现“反反正”之前,我的“正反反”必然会先出现。 事实上,整个游戏的前两次硬币抛掷结果就已经决定了两人最终的命运。只要前两次抛掷结果是“正正”、“正反”、“反正”中的一个,我都必胜无疑,你完全没有翻身的机会;只有前两次掷出的是“反反”的结果,你才会赢得游戏的胜利。因此,我们两人的获胜概率是 3:1 ,我的优势绝不止是一点。 你或许想问,如果已知我的硬币序列是“正反反”,那么你应该选择一个怎样的硬币序列,就能保证获胜概率超过我呢?研究表明,你可以选择“正正反”,这样一来,我们两人的获胜概率将会变为 1:2 ,换句话说你将会有 2/3 的概率获胜。 Using your Head is Permitted 趣题站 2014 年 5 月的趣题对此进行了更深一步的探究。 A 、 B 两人打算玩这么一个游戏。首先, A 选择一个长度为 n 的正反序列,然后 B 再选择另一个长度为 n 的正反序列。之后,不断抛掷硬币,哪名玩家所选的正反序列最先出现,哪名玩家就获胜。我们的问题是,假如两名玩家都采取最优策略的话,对于哪些 n ,游戏对玩家 A 更有利一些(换句话说,玩家 A 拥有超过 50% 的胜率),对于哪些 n ,游戏对玩家 B 更有利一些(换句话说,玩家 […]