Nim 游戏

一共有 n 堆硬币,没堆数量一定,两个人依次取硬币,每次从一堆中取,每次至少取一枚,取到最后一枚硬币的人获胜

分析

用向量(i,j,k)表示堆和堆数

• \((1,1)\) 后手必胜

• \((1,i)\) 先手必胜

  只需取 \((0,i-1)\) 个转化成第一种情况,这样后手必败

• \((i,i)\) 后手必胜

  如果先手取完某一堆则直接胜利,否则若先手取\((j,0)\),后手取\((0,j)\),直到最后变成\((1,1)\),或者\((0,k)\)

• \((i,j)\) 先手必胜

  取\((0,j-i)\),(假定\(j>i\))转化成第三种情况,后手必败

三个堆的情况:

• \((1,1,1)\) 先手必胜

• \((1,1,i)\) 先手必胜

  取\((0,0,i)\)即可

• \((1,i,i)\) 先手必胜

  取\((1,0,0)\)即可,转化成后手必胜的\((i,i)\) 情况

• \((i,i,j)\) 先手必胜

  同理,直接把 j 取掉

• \((i,j,k)\) 不确定了

那么如何必胜呢(可以吗?)?

安全状态

• 对己方取后形成的某个状态

  •若无论对方如何取均不会获胜，状态（对己方）为安全的

  至少有两堆硬币的状态是安全的
  

  •若对方至少存在一种获胜的取法，状态（对己方）为不安全的

  只有一堆硬币的状态是不安全的
  

  •不论对方如何取，己方下一次取后均可变为一个安全状态的状态也是安全的

  •若对方至少存在一种取法，己方下一次取无法变为一个安全状态的状态也是不安全的

如何取胜

让自己取完以后变成安全状态

将每一堆硬币的数量转化成二进制,然后对每一位求和，称其尾数为位和

只有一堆硬币时，位和不可能全是0
每次取硬币时，至少有一个位和发生变化

若所有位和都是 0，则状态是安全的，否则不安全

• 如果当前状态安全，无论怎么取都会不安全

• 如果当前状态不安全，那么存在一种取法使得下一状态安全

  从左到右确定第一个位和为 1 的位，然后找该位数字为 1 的堆，从中取走一些硬币使得状态变成安全状态

python实现

在线运行

RESOURCES