Nim 游戏

有 \(n\) 堆石子，第 \(i\) 堆石子有 \(a_i\) 颗石子，两个人轮流从任意一堆石子中取出任意颗石子，最后把石子取走的人获胜，求谁有必胜策略。

博弈图和状态

我们可以用 \(n\) 个数字表示一个状态，分别表示每堆石子还剩多少颗。我们称一个状态是必胜状态当且仅当玩家在此状态时，存在一种策略可以赢得游戏；反之则是必败状态。状态之间可以形成一张有向图：

对于必胜/必败状态，我们有如下定理：

• 对于 Nim，没有后继状态的状态是必败状态；
• 一个状态是必胜状态当且仅当其可以转移到至少一个必败状态；
• 一个状态是必败状态当且仅当其不能转移到必败状态。

Nim 和

接下来，我们分析 Nim 问题的必胜策略。

定理：当且仅当 \(a_i\) 的异或和不为 \(0\) 时，此状态是必胜状态。

证明

记当前状态下 \(a_i\) 的异或和为 \(s\)。

考虑数学归纳法。

• 必败的最终状态的 \(s=0\)；
• \(s=0\) 的状态只能转移到 \(s\ne 0\) 的状态；
• \(s\ne 0\) 的状态可以转移到 \(s=0\) 的状态；

对于第二个条件，先假设 \(s=0\) 可以转移到一个 \(s=0\) 的状态，容易推出本轮没有取石子，和游戏的规则矛盾；

对于第三个条件，我们记 \(s\) 的最高位是第 \(k\) 位；我们发现一定存在一堆石子 \(a_i\)，满足 \(a_i\) 的第 \(k\) 位是 \(1\)。我们从这堆石子中取走一些石子，使其数量变为 \(a_i\oplus s\)。能够证明 \(a_i\oplus s < a_i\)（因为 \(s\) 会把 \(a_i\) 的第 \(k\) 位变为 \(0\)）。这符合游戏规则。