【专题】Nim博弈
Nim博弈
基本的尼姆博弈（Nim Game）描述如下：
有若干堆各若干个物品，两个人轮流从某一堆取任意多的物品，每次至少取一个，多者不限，最后取光者得胜。
博弈过程如下：
- 对于局面 $ a_1 a_2 a_n = 0 $，无论先手怎么取，必将导致异或和改变为 $ a'_1 a'_2 a'_n = k $ ，而此时必有 $ a_i $ 使得 $ a_i $ 二进制下第k位为1，后手只要将 $ a_i $ 取成 $ a_i k $ ，使得局面重新回到异或和为0，直至最后局面变成 $ (0, 0, , 0) $ ，此时异或和为0。先手必输。
- 对于局面 $ a_1 a_2 a_n $ ，反之，先手必胜。
详细证明见下方Bouton定理。
Bouton定理
Bouton定理：
假设Nim博弈的石子有 $ n $ 堆，第 $ i $ 堆的石子个数我们用 $ a_i $ 表示，则我们可以使用 $ (a_1, a_2, , a_n) $ 表示一个Nim博弈的局面。对于 $ (a_1, a_2, , a_n) $ 的Nim博弈局面，当且仅当 $ a_1 a_2 a_n $ 时（其中 $ $ 是按位异或运算），先手必胜。
简单证明如下：
- 对于 $ a_1 a_2 a_n $ 的Nim博弈局面 $ (a_1, a_2, , a_n) $ ，我们设 $ a_1 a_2 a_n = k $ 。则必存在 $ a_i $ ，其二进制表示在 $ k $ 的最高位上为1（异或运算的性质），且有 $ a_i k < a_i $ 。则对于当前局面下的先手可以通过合法的移动将第堆石子取到只剩 $ a_i k $ 个，那么此时游戏局面变为 $ (a_1, a_2, , a_{i-1},a_i k, a_{i+1}, a_n ) $ 。 而此时 $ a_1a_2 a_{i-1} (a_i k) a_{i+1} a_n = k k = 0 $。得出异或和不为0的局面一定存在合法移动可以变为异或和为0的局面。
- 对于 $ a_1 a_2 a_n = 0 $ 的Nim博弈局面 $ (a_1, a_2, , a_n) $ ，假设我们将第 $ i $ 堆石子由 $ a_i $ 个取到 $ a'_i $ 个，则有 $ a_i a'i $ ，则必有 $ a_1a_2 a{i-1} a'i a{i+1} a_n $ （可用反证法证明）。即异或和为0的局面无论怎样合法地进行移动，都将转变为异或和不为0的局面。
- 对于局面 $ (0, 0, , 0) $ ，其异或和为0，对于先手而言是必输的局面。
- 对于任何异或和不为0的局面，先手只需要按照策略将其转变为异或和为0的局面，就能保证后手永远只能拿到异或和为0的局面。又因为每一次合法的移动都将导致石子个数减少，故总的移动步数是有限的，最终后手将拿到的局面而无石子可拿，故后手必输，先手必胜。反过来即可证，对于任何异或和为0的局面，先手必输。