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

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

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

2006 年，我在博客（当时还是 MSN Space）上发了 《什么是 P 问题、NP 问题和 NPC 问题》 一文。这是我高二搞信息学竞赛时随手写的一些东西，是我的博客中最早的文章之一。今天偶然发现，这篇现在看了恨不得重写一遍的“科普”竟仍然有比较大的阅读量。时间过得很快。《星际争霸》（StarCraft）出了续作，德国队 7 比 1 大胜东道主巴西，《学徒》（The Apprentice）里的那个家伙当了总统，非典之后竟然出了更大的疫情。现在已经是 2022 年了。这 16 年的时间里，我读了大学，出了书，娶了老婆，养了娃。如果现在的我写一篇同样话题的科普文章，我会写成什么样呢？正好，我的新书《神机妙算：一本关于算法的闲书》中有一些相关的内容。我从书里的不同章节中摘选了一些片段，整理加工了一下，弄出了下面这篇文章，或许能回答刚才的问题吧。

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