经典证明: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 时问题是没有解的。

46 条评论

  • whisky

    貌似沙发?

  • Denny

    搶個位子xd

  • SiNZeRo

    膜拜。

  • deducemath

    1、对于楼主“今天”才知道此题我比较惊奇,因为《稳操胜券》下册就有。
    2、小说《深夜小狗神秘事件》用到了这个谜题。

    • ny1050220

      看了你的回复才知道还有《深夜小狗神秘事件》这么个小说 刚刚读到这个谜题那里 还是个不错的小说。《稳操胜券》是本什么书呢?

  • Ekoms

    以前看到过,不过名字叫做“五星上将”,就是每向上超过横线一个单位就是获得一颗星。这个游戏充分说明了“一将成名万骨枯”的道理……

  • exp618

    唔。。。
    “ 现在,我们需要选取一个适当的底数 x ,使得正向移动给多项式带来的变化为 0 。”
    为什么?

  • 落月

    数学无力中。。。

  • error 404

    这种问题居然还能用多项式求解……屌爆了……
    Conway特别喜欢这种……类似细胞机的游戏嘛

  • 果然应如是

    太牛了!!!把实际问题转化成数学问题,通过一个简单的多项式就证明了实际中不可能用实验来完成的问题。太酷了!!!

  • 三维飞机

    最多多长?

  • 齐仁睿

    shift4已出,请速写介绍。

  • biohu

    原来如此!

  • Firm

    哇靠,数学真的是万能的啊,这思维。。

  • MatCxf

    厉害呀佩服呀

  • charlie

    是呀,为什么呢?
    我们需要选取一个适当的底数 x ,使得正向移动给多项式带来的变化为 0

  • chipssy

    回16楼:选取一个适当的底数 x ,使得正向移动给多项式带来的变化为 0,这样做有两个好处:一、任何正向移动都不会改变布局的价值,其它形式的移动都会让价值变小。(这样就限定了布局的价值一开始就必须大于等于1)二、φ2 = 1 – φ ,也才有φ2 + φ3 + φ4 + … = 1(这样可以比较方便地求出布局的价值)。但第一个才是这么做的主要原因。

  • 曦神

    如果n>5呢?
    更准确地说,应该改成“当>=5时,这个问题就不再有解了。”

  • johnson2723

    这问题在两本书里面看过,一本名字忘记了,还有一本是台湾的《科学月刊》

    我自己还试着推导过一次,可以证明对于赋予任何值的格子都不可能,不一定要用黄金分割。

    设目标格子的值为(x0),离目标格子距离n步的格子的值为xn,且对于任何n有xn=xn-1+xn-2

    考虑第二行后面所有格子的值:
    (1)x2+3*x3+5*x4+7*x5+…
    上式=(x2+x3)+2*(x3+x4)+3*(x4+x5)+4*(x5+x6)+…
    =x1+2*x2+3*x3+4*x4+…(2)

    (2)-(1)=x1+x2-x4-2*x5-3*x6-…=x0-(x4+2*x5+3*x6+…)=x0-((x5+x6)+2*(x6+x7)+3*(x7+x8)+…)
    =x0-(x5+3*x6+5*x7+…)

    被减数是目标格子的值,减数是第五行之后所有格子的值,因为(2)式等于(1)式,所以差为0,x0=(x5+3*x6+5*x7+…),证毕。

    此外,有没有有没有适用于无穷多棋子情况的解?(就像无穷囚犯问题http://www.matrix67.com/blog/archives/444那样)

    1+3*x

  • zhang

    谁是conway,Damian Conway?

  • hcz

    回20楼:应该是John Conway,就是研究细胞自动机的那位

  • StormRaiser

    用无穷多步把棋子走到第五格的方法太神了……

  • abcd

    不愧是Conway。。。

  • xiaoluo

    博主,x值的不同怎样体现棋盘的棋子布局和个数?

  • jialrs

    是个关于必要条件的证明吧,必要条件不成立,原命题(n>=5 有解)当然不成立。。。
    证明很经典啊。。。。
    不过话说,n<5时怎么找出解的啊?别告诉我是暴力的。。。。

  • xiaoxue

    从19L得到的灵感,其实我们要证明x5+3×6+7×7+9×8+…<=1
    然后Xn=Xn+2 + Xn+1
    这样:
    x5+3×6+5×7+7×9+…
    =(x5+x6)+2(x6+x7)+3(x7+x8)+4(x8+x9)+…
    =x4+2×5+3×6+4×7+…
    =(x2-x3)+2(x3-x4)+3(x4-x5)+4(x5-x6)+…
    =x2+x3+x4+x5+x6+…
    =(x0-x1)+(x1-x2)+(x2-x3)+(x3-x4)+(x4-x5)+…
    =x0
    =1
    Q.E.D.
    这样对不对?

  • johnson2723

    回23L,n=1,2,3,4时可以用逆推法来办,就是想办法形成n-1时的状态,只是往前一格而已。

  • zst_0110

    纯粹前来实验头像。。。

  • luowei1428

    92年用作了IMO国家队的选拔试题

  • Maigo

    当年我好像是在一个日文网站上看到这道题的,还用象棋子摆了半天

  • pseudonoise

    精彩,本来想问问题的,但是想明白了

  • Safari

    这解法。。。牛爆了

  • reach334

    19L的差分方程确实是更一般的,其通解其实就是黄金分割的幂的线性组合。
    Conway的证明只取了其中一个黄金分割的幂,这样可以降低证明的复杂度,反正证伪只需要有一个反例就够了。

  • cervelo

    太牛了!!!把实际问题转化成数学问题,通过一个简单的多项式就证明了实际中不可能用实验来完成的问题。太酷了!!!

  • zaxs

    我是在搜索您的一篇文章时来到这里的。我记得您曾写过一篇关于斐波那契数列与黄金分割数的文章,里面还有动态演示的图片,但是我现在找不到了,能告诉我在哪吗?

  • AllenHak

    Hello there! propecia best online pharmacy discount best online pharmacy

  • SqrtSecond

    5个棋子在初始有无限枚棋子时是可以达到的

回复给 deducemath 取消回复

8  ×    =  32