先说结论:
\(a_1\oplus a_2\oplus ...\oplus a_n=0\)
此时先手必败
\(a_1\oplus a_2\oplus ...\oplus a_n \ne 0\)
此时先手必胜
证明:
我们知道在nim游戏中,每堆都是\(0\)时,此时轮到的人失败
而\(0\oplus 0\oplus ...\oplus 0=0\)
所以只要一直让\(a_1\oplus a_2\oplus ...\oplus a_n=0\),最后一定会出现全\(0\)局面
为此要证明两点:
第一点:
\(a_1\oplus a_2\oplus ...\oplus a_n \ne 0\) 时,一定可以通过一次操作,让\(a_1\oplus a_2\oplus ...\oplus a_n = 0\)
设\(a_1\oplus a_2\oplus ...\oplus a_n = x\)
且\(x\)最高位为第\(k\)位
则一定有一个\(i\),保证\(a_i\)二进制状态下的第\(k\)位为\(1\)
则有\(a_i \oplus x< a_i\)
这点很好证明:
设\(a_i\)后\(k\)位为\(1\)后面一大坨
\(x\)的后\(k\)位同样为为\(1\)后面一大坨
所以两者异或,第\(k\)位没了,剩下的肯定小于\(a_i\)
所以有了这点,我们不妨让\(a_i\)变成\(a_i \oplus x\),即在第\(i\)堆拿去\(a_i-(a_1 \oplus x)\) 个
所以原来\(n\)堆的异或变成了:
\(a_1\oplus a_2\oplus ...\oplus a_i \oplus x \oplus ...\oplus a_n\)
我们知道原来这n堆异或为\(x\),即\(a_1\oplus a_2\oplus ...\oplus a_n = x\)
现在又多了一个\(x\),\(n\)堆的异或变成了\(0\),目的达到了
第一点证毕
接下来还要证明一点
第二点:
当\(a_1\oplus a_2\oplus ...\oplus a_n=0\) 时,不管如何取,取之后n堆异或一定不是\(0\),即 \(a_1\oplus a_2\oplus ...\oplus a_n \ne 0\)
这里可以用反证法:
设在第\(i\)堆取走若干个,会使其变成\(a_i'\)
假设取走后\(n\)堆异或还是\(0\):
则\(a_1\oplus a_2\oplus ...\oplus a_i' \oplus ...\oplus a_n=0\)
和原来的\(a_1\oplus a_2\oplus ...\oplus a_i \oplus ...\oplus a_n=0\) 比较
我们可以让两个等式左右两边异或起来
发现一个神奇的东西:
\(a_i \oplus a_i' = 0\)
即为$a_i=a_i'\ \ $明显矛盾
所以第二点证毕
综上可以得出:
若\(a_1\oplus a_2\oplus ...\oplus a_n=0\)
则先手无论如何也无法让\(n\)堆异或还是为\(0\),所以后手每次接到先手操作的结果都是\(n\)堆异或不等于\(0\),而TA可以通过上述第一点的方式再次让\(n\)堆异或为\(0\),以此类推,最后先手将受到\(n\)堆全部为\(0\),就无了
若\(a_1\oplus a_2\oplus ...\oplus a_n \ne 0\) ,还是一样的道理,这次是后手无了