经典证明: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 […]

16 年后重谈 P 和 NP

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

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

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