Nim游戏

假设开始有两堆石子， 一堆石子是3， 另一个是2.
那么先手必胜。原因：1号先从第一堆石子里面拿一个石子。两堆石子就都是2颗了。之后，只要先手根据后手的操作进行镜像的操作，就能保证自己的胜利。如果后手取一颗，先手也在另一堆里面取一颗；后手取两颗，先手在另一堆里面取两颗。总能保证先手取完最后一颗石子。

先手必胜状态：可以走到某一个必败状态
先手必败状态：走不到一个必败状态

结论：


第一个状态表示终点的异或值一定是0，表示必败态，因为无法走到任意一个必败态
第二个状态表示必胜态，因为，可以想办法将当前状态走到某一个必败态。
如何证明在当前状态取走若干个石子之后，可以是所有石堆异或值为0？

假设x的二进制表示中最高一位1在第k位，那么在a1, a2,an中必然存在一个ai，它的第k为也是1.
假设ai = 1100 101010001;
x = 101010100;
ai ^ (异或)x < ai; 第k位变为0了，所以等式成立。
所以从第i堆里面取出ai - ai ^ x之后， 式子2，变为
a1^a2 ^a3 .....an = x != 0
变为
a1^a2 ^a3 ...^(ai - (ai - ai ^ x)).…^an = x ^ x = 0
能从当前态转换为某个必败态，因此当前为必胜态。
当前存在一种取石子方式使得当前状态变为必败态

证明第一个式子就是为什么必败态无法转换到另一个必败态。
思路和第二个式子一样。用反证法

因为ai’表示的是取走了一部分的石子数，因此ai’ < ai;和结果矛盾。

结论：当先手的状态是全0状态，即状态1时，他任取石子都会变成状态2，即失去必胜状态； 当先手的状态是非全0状态，即状态2时，他可以通过取石子变成状态1，即全0状态；