经典证明：Conway的士兵

    今天听说了 Conway's Soldiers ，这是 Conway 大牛在 1961 年提出的一个数学谜题（似乎 Conway 的出镜率也太高了），我觉得非常有意思，在这里跟大家介绍一下。内容基本上来自于 Wikipedia 的相关页面。

    假设有一个无限大的棋盘。棋盘上可以放置一些象征着士兵的棋子。一个棋子可以跳过并吃掉和它相邻的一枚棋子（就像孔明棋一样）。这是棋子的唯一一种移动方式。现在，在某个位置画一条无限长的水平线，你需要在水平线下面放置足够多的棋子，使得他们前仆后继地往水平线上方跳，最终能够跳到水平线以上 n 个单位的位置。

    如图所示，当 n = 1 时，两个棋子就够了。当 n = 2 时，我们需要 4 个棋子。当 n = 3 时，最少需要 8 个棋子。

    我们还能让士兵们冲到更远吗？可以的。下图显示的就是 n = 4 的最少棋子摆布方案，它一共要用 20 枚棋子（看看你能不能看出具体的移动步骤）。有趣的是， Conway 证明了下面这个或许有些不可思议的事实：当 n = 5 时，这个问题就不再有解了。换句话说，无论用多少个初始棋子，我们都不可能冲到 5 个单位远的位置去。这个证明过程非常神奇，它竟然和黄金分割莫名其妙地扯上了关系。

    我们给每个格子标一个关于 x 的单项式。把目标格子标记为 x⁰ ，也就是 1 ；一个格子离目标格子有多少步（相当于 manhattan 距离），就给这个格子标上 x 的多少次方。于是，整个棋盘就变成了下面这样。棋盘上的若干棋子形成的布局，也就对应了一个关于 x 的多项式。例如，下图中的 6 枚棋子就对应了多项式 x⁴ + 3 · x⁵ + 2 · x⁶ 。

    每次移动棋子，我们都会改变一个棋子的位置，同时从棋盘中拿掉另一个棋子，从而让整个多项式发生变化。我们把棋子的移动分成三类：正向移动、中性移动、背向移动（分别如上图中左、中、右三个棋子跳跃的例子）。所谓正向移动，也就是朝着目标点的方向跳跃，棋子落点处的指数比出发点的指数更小。假如棋子的出发点所在位置是 xⁿ，那么这次跳跃给整个多项式带来的变化就是减去了一个 xⁿ ，加上了一个 x^n-2 ，并且还减去了一个 x^n-1 。我们可以记作 x^n-2 (1 - x - x²) 。中性移动就是指一个棋子从标有 xⁿ 的格子跳到了另一个标有 xⁿ 的格子，和目标点的距离并未变化，仅仅会让棋盘上少一个棋子 x^n-1 。因此，这种移动给整个多项式带来的变化就是 - x^n-1 。背向移动则是往远离目标点的方向跳跃，它给多项式带来的变化则是 - xⁿ + xⁿ⁺² - xⁿ⁺¹ ，即 xⁿ (x² - x - 1) 。

    现在，我们需要选取一个适当的底数 x ，使得正向移动给多项式带来的变化为 0 。为此，我们需要让 x 满足 1 - x - x² = 0 ，解得 x = (±√5 - 1) / 2 。我们选取其中的正数解 (√5 - 1) / 2 。出人意料的是，它正是神奇的黄金分割数 φ ≈ 0.618 。

    这样，棋盘的每个格子都对应了一个形如 φⁿ 的正实数，其中目标点是 φ⁰ ，也就是 1 。定义一个棋局的价值为各个棋子位置上所对应的正实数之和。任何正向移动都不会改变布局的价值，其它形式的移动都会让价值变小。我们的目标就是把整个阵型的价值变成 1 （或者更大，如果最后还有残余棋子的话）。

    注意 φ 的一些有趣的性质。由于 φ² = 1 - φ ，不断在等式两边乘以 φ ，我们还可以得到 φ³ = φ - φ² ，φ⁴ = φ² - φ³ ， φ⁵ = φ³ - φ⁴ 等等。把等式左边全部加起来，也就得到 φ² + φ³ + φ⁴ + … = 1 了。

    当 n 等于 1 时，水平线以下第一行的格子的价值总和是 φ + 2 · φ² + 2 · φ³ + 2 · φ⁴ + … ，第二行每个格子的价值分别是第一行对应格子的 φ 倍，第三行格子的价值则再乘以 φ ，以此类推。因此，水平线以下的所有格子的总价值为：

        (φ + 2 · φ² + 2 · φ³ + 2 · φ⁴ + …) (1 + φ + φ² + φ³ + …)
     = (φ + 2)(1 + φ + 1)
     = (φ + 2)²
     = φ² + 4 φ + 4
     = 5 + 3 φ ，

    其中，最后一步再次用到了 φ² = 1 - φ 。

    当 n = 2 时，水平线离目标点的距离增加一个单位，从而导致每个格子的价值都乘以了一个 φ ，于是水平线下的所有格子的价值总和就是 (5 + 3 φ) φ = 5 φ + 3 φ² = 3 + 2 φ 。类似的， n = 3 时水平线下方的格子总价值为 (3 + 2 φ) φ = 3 φ + 2 φ² = 2 + φ ， n = 4 时这个值变为了 (2 + φ) φ = 2 φ + φ² = 1 + φ ， n = 5 时这个值变为了 (1+ φ) φ = φ + φ² = 1 。这表明，当 n 等于 5 时，如果在水平线以下的所有格子里都放上棋子，总价值正好为 1 。当然，棋子的数量不可能是无限的，因而初始布局的价值是严格小于 1 的，我们不可能把它变为一个价值大于等于 1 的棋局。这就说明， n = 5 时问题是没有解的。