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

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

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

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

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

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

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

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

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

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

    (φ + 2 ・ φ2 + 2 ・ φ3 + 2 ・ φ4 + …) (1 + φ + φ2 + φ3 + …)

          = (φ + 2)(1 + φ + 1)

          = (φ + 2)2

          = φ2 + 4 φ + 4

          = 5 + 3 φ ，

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