浅谈Nim游戏
-
首先，我们需要了解 \(Nim\) 游戏是什么东西。
-
\(Nim\) 游戏指：两个人，有 \(n\) 堆数，每堆有 \(a_i\) 个，每次可以且仅可以取一堆中的若干个数，求问先手有没有必胜策略（当然两个人都足够聪明）。
-
首先，先研究显然的必胜策略。比如，我们要得到 \(0\) 这个数，那么当你取完时还剩下 \(0\) 个。
-
然后，我们通过最后的这个必胜状态，往前递推找出其余的必胜状态。
-
显然博弈论是必然会出现循环节的，如果每次都可以取到当前这个循环节上的必胜状态，并且让你的对手能达到的下个状态全部都是必败状态，那样你就稳赢。
-
接着，我们来分析 \(Nim\) 游戏这道题，我们先考虑什么状态下是必胜的：
-
当 \(n=1\) 的时候，很显然先手必胜，因为先手一次性取完即可。
- 当然，这里当 \(n ≠ 0\) 时，先手必败。
-
当 \(==2\) 的时候：我们就需要考虑一堆的石头和另一堆的石头相不相等。
-
如果一堆的石头和另一堆相等，那么不论先手取什么，后手都只需要跟着先手取相同的个数就行了。所以很显然就是先手必败。
- 此时我们可以考虑为：\(a_1\operatorname{xor} a_2 = a\)。
-
如果一堆的石头和另一堆不相等，那么先手就取 \(|a_1-a_2|\)。就必胜了。