【未完待续】基础博弈论
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/
如果未注明出处,复制公开后需将注明本博客链接。打赏作者