博弈论学习笔记

挖个巨坑，慢慢填。

从 Nim 游戏入手

问题：有 $n$ 堆石子，第 $i$ 堆石子有 $s_i$ 个，两个人轮流取石子，每人每次只能从一堆中取任意数量的石子，可以取完，不能不取。问先手必胜还是必败。

前置知识：

1. 异或 $\oplus$：有两个数均为 $0$ 或 $1$，若它们相等则异或结果为 $0$，不相等结果为 $1$
2. 按位异或 $\oplus$：将两个正整数分别表示成二进制，对应位进行异或。易证，按位异或满足交换律、结合律，同时有自反性，即 $a\oplus a=0$
3. 异或和：若干个正整数 $a_1,a_2,a_3,\ldots,a_n$ 的异或和为 $a_1\oplus a_2\oplus a_3\oplus\ldots\oplus a_n$。容易发现，若 $s$（二进制）中某一位为 $1$ 的数字个数为奇数，则异或和中该位为 $1$；若为偶数，则异或和中该位为 $0$

结论：若 $s$ 的异或和为 $0$，先手必败，反之则先手必胜。

感性理解一下。考虑只有两堆的特殊情况，如果两堆的数量相等，那么先手必败，策略为：先手从一堆中取若干个，后手从另一堆中取相同个数，则易证一定被后手取完。反之，如果两堆的数量不等，那么先手必胜，策略为：先从多的那堆里取若干个，使两堆数量相等，接下来同上（后手变为上面的先手）。

考虑用异或来解释。若先手取时两堆不相等（即异或和不为 $0$），则从多的那堆里取若干个使两堆相等（使得异或和变为 $0$）。接下来无论后手怎么取，一定会导致两堆数量不相等（使异或和不为 $0$）。先手从另一堆中模仿后手操作，使两堆再次相等（异或和重新变成 $0$），以此类推。

有了以上感性理解，我们就可以尝试推广到 $n$ 堆的普遍情况。

定理一：当异或和不为 $0$ 时，一定存在一种取石子方式使得异或和变为 $0$。

证明：

若我们所在的状态满足 $s_1\oplus s_2\oplus\ldots\oplus s_n=m (m\ne 0)$（$s_i$ 表示第 $i$ 堆的石子数），则$s_1\oplus s_2\oplus\ldots\oplus s_n\oplus m=m\oplus m=0$（自反性），所以只要随便选择一堆 $s_i$ 变为 $s_i\oplus m$ 即可。但是由于要“取”石子，所以要求变化后石子数必须减少，那么是否一定存在一堆 $s_i$ 满足 $s_i\oplus m<s_i$ 呢？答案是肯定的。

$m$（二进制）的最高位（设为第 $k$ 位）的 $1$ 一定是由 $s$ 中奇数个 $1$ 得来的，也就是在 $s$ 中一定存在至少一个第 $k$ 位为 $1$ 的数。随便选一个，假设为第 $i$ 个，则将上式最后的 $\oplus m$ 与 $s_i$ 结合，结果一定会比 $s_i$ 小。因为 $s_i$ 比 $k$ 高的位不变，第 $k$ 位由 $1$ 变为了 $0$，剩下的无论怎么变结果都会比 $s_i$ 小。

所以只要异或和不为 $0$，一定可以通过选合适的一堆取若干个石子使得 $s_i\to s_i\oplus m$，则异或和 $m\to 0$。

定理二：当异或和为 $0$ 时，无论如何取石子，取后异或和都将不为 $0$。

证明：

假设取后异或和仍然为 $0$，则 $m=0$，又因为 $m$ 只能选一堆结合，所以 $s_i$ 只能不变。但题目要求必须取，与假设矛盾，所以取后异或和一定不为 $0$。

综上所述，当先手处于异或和不为 $0$ 的状态时：

1. 先手一定可以通过一定方式变成异或和为 $0$（定理一）
2. 此时后手只能变成异或和不为 $0$（定理二），接下来重复步骤 1
3. 胜利状态的 $s$ 全为 $0$，异或和为 $0$，而对手只能变成异或和不为 $0$，所以永远取不到胜利状态
4. 由于每步石子数必然会减少，最终一定会达到胜利状态，则胜利状态必然由先手取到

若先手处于异或和为 $0$ 的状态，则任何操作都将导致异或和不为 $0$，接下来后手如上操作，则后手必胜。

未完待续，不定期更新。