$NIM$游戏小总结

$umm$可能之后会写个博弈论总结然后就直接把这个复制粘贴上去就把这个删了

但因为还没学完所以先随便写个$NIM$游戏总结趴$QAQ$

首先最基础的$NIM$游戏:有$n$堆石子,每次可以从一堆中取若干个,求最后谁胜利

这种有个结论,是说当开局所有数异或起来不为0时先手必胜

证明在这里写了下,懒得再写遍了挺显然的$QwQ$

(大概$get$了一下$SG$函数之后来瞎$upd$下,,,

就,这儿其实是可以用$SG$函数解释的

简单来说,不难得到$SG(x)=x$,挺显然的?就,因为可以取任意多个,于是有$SG(x)=mex(SG(x-1),SG(x-2),...,SG(0))$,数学归纳法即可$QwQ$

又有$SG(G)=SG(x_{1})$^$SG(x_{2})$^$...$,于是就有当$x_{1}$^$x_{2}$^...^$x_{n}\neq 0$时先手必胜,否则必败

然后说下变式昂

变式1:每次取的石子数量有上界$m$

$umm$就是一个$bash\ game$+$NIM\ game$(关于$bash\ game$的话放个最$easy$的入门题趴$QwQ$

直接把所有值对$m+1$取膜就好,证明十分显然?就一定能在先手/后手的操纵下就像$bash-game$中一样使得每堆石子的数量都<=$m$,这时候就相当于没有这个$m$的限制了就当普通$NIM$游戏做就好了$QwQ$

变式2:每次可以从$k$堆中取若干个

基础$NIM$游戏可以当做是这个变式的一个$easy$版情况?就相当于是$NIM_{1}$嘛

那就考虑能不能用一点儿,类比的思想,从类似的角度考虑这个问题的通解$QwQ$?

于是不难得出结论所有数在$k$进制下做不进位加法不为0时先手必胜

再来瞎证下趴$QAQ$

按之前证$NIM$游戏结论时候的流程,依然是考虑当在$k$进制下做不进位加法不为0时的情况,考虑如果能取一些石子使得变为在$k$进制下做不进位加法为0

这时又是两种情况

第一种是没有石子剩余了,欧克赢了,不说

第二种是还有石子剩余,因为最多只能从$k$堆中拿,所以不可能出现后手拿了之后依然是$k$进制下做不进位加法答案是0的情况,即一定又能回到最开始

那就相当于现在只要能证,在不进位加法不为0的情况下能取出一些石子使它变为等于0的状态就好

考虑对所有数字都$k$进制分解,开个数组$a_{i,j}$,表示第$j$个数在$k^{i}$下的取值,再开个$sum_{i}$表示$\sum a_i\ mod\ k$,显然对每一位$i$,取出$sum_{i}$就好

显然是可以达成的

证毕!(好像表述不太清,,,算了不管了$TT$

变式3:阶梯博弈

先说下这类题是啥$QwQ$

大概就是有个高度递增的楼梯,每一级上都有若干个球,每次操作可以选择一级楼梯,选择上面的若干个球移动到边上更低的那一极去,当移动到地面(第0级楼梯)的时候就不能操作了

这题也是有个结论,是说可以忽略偶数级台阶,剩余的奇数级构成的$NIM$游戏的结果就是这个题的结果

知道结论了的话证明还是不难的$QwQ$,下面瞎证下趴$QAQ$

首先当所有球都到0级楼梯时就不能移动了,是在偶数级楼梯上的

然后当对方移动了偶数级楼梯的时候,比如将$d$个球从第$2n$级到了第$2n-1$级,就把第$2n-1$级上的$d$个球移到第$2n-2$级去

这样就可以保证,从奇数移至偶数,相当于是拿走,从偶数移至奇数,相当于没有意义

如果能$get$这点的话也就不难想到只考虑奇数层的时候就是个普通的$NIM$游戏了呢$QwQ$

例题:

[X]$poj1704$

巴特西

$NIM$游戏小总结

最新文章

热门文章