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