Nim游戏的定义是这样的：

有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

Nim游戏的结论:

设有n堆石子 每堆石子的数量为 a[1],a[2],a[3]......a[n];

倘若a[1]^a[2]^a[3]^a[4]......^a[n-1]^a[n]=0 那么先手必败
倘若a[1]^a[2]^a[3]^a[4]......^a[n-1]^a[n]!=0 则先手必胜

证明如下:
1. 要证 当a[1] ^ a[2] ^ a[3] ^ a[4]...... ^ a[n-1] ^ a[n] = x 时可以通过拿一堆中的石子使得a[1] ^ a[2] ^ a[3] ^ a[4]...... ^ a[n-1] ^ a[n] = 0

已知 0 ^ 0 ^ 0 ^ 0 ^ ....0 ^ 0 = 0 那么假设 a[1] ^ a[2] ^ a[3] ^ a[4]...... ^ a[n-1] ^ a[n] = x

那么假设这个x的二进制表示的数最高位的 1 在第 k 位 那么 a[1] , a[2] , a[3] , a[4] ...... a[n-1] , a[n]

中一定会存在一个数 a[i] 的第 k 位是 1

由异或运算的法则我们可知 a[i] ^ x < a[i] 那么我们就可以从 a[i] 这堆石子中拿走 a[i] - a[i] ^ x 个石子

那么此时剩下的石子就变成了 a[i] - ( a[i] - a[i] ^ x) = a[i] ^ x

即原本的 a[i] 变成了 a[i] ^ x

由 a[1] ^ a[2 ]^ a[3] ^ a[4]...... ^ a[n-1] ^ a[n] = x

可知 a[1] ^ a[2].... ^ a[i] ^ a[i+1]...... ^ a[n-1] ^ a[n] ^ x 就是 x ^ x=0

1. 要证当a[1] ^ a[2] ^ a[3] ^ a[4]...... ^ a[n-1] ^ a[n] = 0时 不管怎么拿石子 拿完后的 a[1] ^ a[2] ^ a[3] ^ a[4]...... ^a[i]^a[i+1].... ^ a[n-1] ^ a[n] != 0 始终成立

证明如下:

记作一式: a[1] ^ a[2] ^ a[3] ^ a[4]…a[i] ^ a[i+1] … ^ a[n-1] ^ a[n] = 0

那么改变后的石子堆为 记作二式: a[1] ^ a[2] ^ a[3] ^ a[4]...... ^(a[i]一瞥) ^ a[i+1].... ^ a[n-1] ^ a[n] = 0

将一式与二式取 ^ 可得 a[i]^(a[i]一瞥) = 0 由此我们可以推断 a[i] 与 (a[i]一瞥) 相等 即没有操作这与假设矛盾

因此 a[1] ^ a[2] ^ a[3] ^ a[4]...... ^(a[i]一瞥) ^ a[i+1].... ^ a[n-1] ^ a[n] 一定不等于 0

证毕!!!!

因此我们可以看到 当先手处于必败态a[1]^a[2]^a[3]^a[4]......^a[n-1]^a[n]=0而取石子后留下的石子堆异或的结果一 定不会是0 那么留给对方的就是必胜态 自己必输

而当先手处于必胜态时 即 a[1]^a[2]^a[3]^a[4]......^a[n-1]^a[n]!=0 那么一定可以通过取石子将a[1]^a[2]^a[3]^a[4]......^a[n-1]^a[n]变成 0 那么留给对方的就是必败态 自己必胜