Nim 博弈（证明）

题目：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则此人输掉了游戏

以下为针对这个问题的三条定理；(以下设每堆数目为a1~ai)

①0^0^0^0^0^0^0...^0=0(当所有堆都为0时);

②如果当前a1^a2^a3^ai...^an=x; 则可通过一次操作从某堆中取出石子将其转变为 a1^a2^a3^ai'...^an=0;

③如果当前a1^a2^a3^ai...^an=0；则不能通过一次操作再使a1^a2^a3^ai'...^an=0

 对②证明：由于异或值为x，那么对于a1~an中一定存在ai（二进制）的最高位为1（因为对于异或只有存在1和0才能得1）.

那么我们就可以去ai堆，使ai堆只剩下ai^x（显然：ai>ai^x     因为ai和x的最高位都为1，异或后为0）

对 ③证明：假设能通过一次操作使a1^a2^a3^ai...^an=0仍成立；操作后为a1^a2^a3^ai'...^an=0；将两个红色的式子左右两边分别异或左侧a1^a1^a2^a2...^ai^ai'^an^an其中ai^ai一定含1（二进制），而a1^a1..an^an的值一定为0，所以左侧结果非0；而右侧0^0为0；左右两边不相等，所以假设不成立；因此不能通过一次操作使a1^a2^a3^a4...^an=0继续保持

现在我们由以上的3个定理，给出石子a1~an，假设此时a1^a2^a3..an=x(非0)；根据定理②我们就可以 操作一步使a1^a2^a3..an=0;根据定理③对手只能将当前结果变为x(非0)；重复执行以上的操作，一定会存在我执行完操作后，每堆石子都为0；对手不能操作，我们胜利。

结论：采取最优策略，如果a1^a2^...an=x(非0)则我方能够获胜，a1^a2^...an=0对手获胜。（总结一下队长讲的^^）

本文地址：https://blog.csdn.net/weixin_45758110/article/details/108562733