博弈论 笔记

挖坑待补。

$\mathbf{N}$ 态：当前手胜利的局面。

$\mathbf{P}$ 态：当前手失败的局面。

K-Nim 游戏

描述

有 $n$ 堆石子，先手和后手轮流取，每次选择 $1\sim k$ 堆，每堆取走至少一个，不能操作者败。

解法

设 $a_{i,j}$ 表示第 $i$ 堆石子数量第 $j$ 位二进制的值，若 $\mathrm{\forall }j,\sum _i{a}_{i,j}\equiv 0(\mathrm{mod}k+1)$，则先手必败。

证明：

• 记 $\mathrm{\forall }j,\sum _i{a}_{i,j}\equiv 0(\mathrm{mod}k+1)$ 为条件 $A$。

• 最终的 $\mathbf{P}$ 态满足条件 $A$，因为 $a_i$ 全为 $0$。

• 对于任意一个 $\mathbf{N}$ 态不满足条件 $A$，考虑 $\mathrm{P}$ 态当前手取的石子堆二进制最高位，这一位必然发现改变，改变值就是取了多少堆有这个最高位的，如果这一位在 $\mathbf{N}$ 态中仍然为 $mod(k+1)=0$，那么说明取了 $k+1$ 堆石子，不符合题意。

• 考虑 $\mathbf{N}$ 态当前手怎么取，同理只需要让最高位的和对应的若干堆全部变成 $0$，此时这些堆的物品个数的最高位的 $1$ 可以任意下放到低位，和别的凑成 $mod(k+1)=0$，即可让下一手变成 $\mathbf{P}$ 态。