对于 对石子,每堆有
个,每次可以从一堆取走任意多个,求每个状态是必胜还是必败。
结论是当且仅当 ^
^
^
时必败。
证明:
1:若 ^
^
^
,那么操作后
^
^
^
。因为若存在
满足
^
^
^
^
^
,那么将两式异或,则
^
,矛盾。
2:若 ^
^
^
,那么存在
满足
^
^
^
^
^
。考虑 k 的最高位,则一定有某个
,它的这一位不为
。那么
^
。那么将
取走
^
,则
^
^
^
^
^
。
而只有异或和为 的时候游戏才可能结束,故结论成立。