0%

Nim

Nim游戏

$n$堆石子,每堆$a_i$个,两个玩家轮流取走任意一堆中的任意多个石子,不可不取,取走最后一个物品的人获胜

Nim和

定义Nim和为$S=a_1⊕a_2⊕…⊕a_n$

则有 Nim博弈先手必胜,当且仅当$S=0$

证明

  • 都被取光,显然为必败状态,S=0
  • 若S=x!=0,若x二进制最高1位为k,则必然有一$a_i$其k位为1显同为最高位为1,显然有$a_iXORx<a_i$,所以我们可以取走一部分石子,使得最终$S_{final}=SXORS=0$
  • $S=0$时,可证,无法取任何石子,使得$S_2=0$

由上三点可知

  • $S!=0$时总能在下一步转化为$S=0$
  • $S=0$总不能转化为$S=0$

即,$S!=0$为必胜,故因$S=0$全部后继为必胜,$S=0$必败

既证: Nim博弈先手必胜当且仅当$S_{Nim}=0$