经典证明: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 的单项式。把目标格子标记为 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 – φ 。

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

发表评论

  ×  2  =  14