Nim博弈

题意简述

有n堆棋子，每一次可以从一堆中取走不少于1的任意个棋子。不能取的一方输。问先手是否必胜。
（所有博弈的前提是两者都采取最优策略）

定理

设第i堆中有 $a_i$个棋子。

若 $a_1 xor a_2 xor ... xor a_n\ne0$ 则先手必胜，否则后手必胜。

我在看到这条结论的时候想了好久，为什么要用xor。后来才发现了其中的奥妙

奥妙

现在我们的序列如果是xor不等于0的，那么绝对有一种取法可以将其xor变为0。而若xor是0，无论如何取xor都不等于0。而在此期间这个序列的总和是减少了的。

又由于全部为0的情况下是必输态，此时xor=0，所以可以推得xor=0就是必输态。

证毕。

阶梯博弈问题

就是Nim的一个变种。

由于要全部取到0号阶梯。0号阶梯是偶数号，所以我们要在每一步中，尽量将奇数号阶梯的石子移走。从而使得奇数号xor=0。此时对手就是必输态。

如果对手从偶数号移到奇数号，我们将其重新从奇数号移至偶数号即可，留给对方必输态。

如果对手从奇数号移到偶数号，我们绝对能用 奇数号移至偶数号 的方法将奇数号的xor重新归0，留给对方必输态

而由于每一次移动都是往最低处去的，所以最终一定会将全部石子移动至最低处，并且可以确保必输太留给对手。

SG函数

未完待续。。。

本文链接：http://kaispace.com.cn/index.php/archives/652/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者