首页 > 其他分享 >nim游戏必胜策略的证明

nim游戏必胜策略的证明

时间:2023-02-02 10:55:21浏览次数:36  
标签:... 游戏 nim ne 必胜 异或 oplus 位为

先说结论:

\(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\) ,还是一样的道理,这次是后手无了

标签:...,游戏,nim,ne,必胜,异或,oplus,位为
From: https://www.cnblogs.com/StevenZC/p/17085255.html

相关文章