各种花式取石头~
巴什博奕
单堆,轮次限制
一堆石头个数为n,两人轮流取,一次至少取一个最多取r个,最后拿光的获胜,判断先手和后手的胜负情况
分析:每次最多取r个,那么双方一轮内总可以控制取的总数是(r+1)。
那么先手的任务是维持剩余石头是(r+1)的倍数,可以把这种状态视为平衡态,即n % (r+1) = 0
。
这样总是由后手破坏平衡,从而先手最终收尾获胜。
如果起始时石头总数对(r+1)有余数,那么先手把这些取光可以必胜。
如果起始时石头总数恰好是(r+1)的倍数,那么先手必然会破坏平衡,后手可以必胜。
变形:
1.两个人轮流从0开始加1~10之间任意数字,先加到100的人获胜
问题转化为一堆100个石头,每次最多取10个
尼姆博弈
多堆,每次单堆不限
m堆石头个数分别为n1,n2,…,nm,两个人轮流取,一次只能选一堆,至少取一个至多取全部,最后拿光的获胜,判断先手和后手的胜负情况
分析:
设函数f(n1,n2,…,nm)表示m堆时先手是否必胜
问题的重点是如何迫使对手给自己留下最后的一堆。分析一堆两堆时的简单情况
1 | f(n) = true; |
考虑每堆个数的二进制形式,每个数位上进行模2加法,如果各个数位的结果都是0,那么视为平衡态。模2加法等效于异或,即n1^n2^...^nm = 0
。
如果初始状态是非平衡,那么先手任务是取一定量石头转化为平衡态,从而可以必胜。反之初始即平衡那么后手必胜。
证明:
引理1:平衡状态下,进行任何下一步操作将会打破平衡
引理2:非平衡状态下,总可以进行一步操作到达平衡状态
详细可参见维基百科
变形:
1.任何大于1的自然数都可以分解成质数的乘积,给定一个数两人轮流用质数的幂次去除,先得到1的获胜
例如720=24*32*51,问题转化为三堆石头分别为4,2,1
延伸
1.变更胜负条件,取最后一个石头的负
问题的重点是如何给对手留一个
1 | f(1) = false;//别无选择,先手必败 |
结论:有奇数个堆,并且每堆为1,这种要特殊考虑,其余情况和基本问题结论一致
广义分析
上述两个问题可以统一在一个框架下。
m堆石头个数分别为n1,n2,…,nm,两个人轮流取,一次最多可以取k堆,每堆至少取一个至多取r个,最后拿光的获胜,判断先手和后手的胜负情况
此时的平衡条件是,n % (r + 1)的二进制表示,每个数位进行模(k+1)加法,每个数位为0
结论:先手在非平衡状态下必胜,后手在平衡状态下必胜
斐波那契博弈
单堆,轮次2倍限制
一堆石头个数为n,两人轮流取,第一次不能取光,每轮后取的不能超过先取的两倍,最后拿光的获胜,判断先手和后手的胜负情况
当n是斐波那契数时,先手必败,可以用数学归纳法证明
反之根据齐肯多夫定理,任何正整数可以表示为若干不连续斐波那契数之和
看成多堆,每堆是斐波那契数,且不连续,因此先手上来先拿光最小的,后手只能在下一个拿,并且拿不完,后手进入必败
版权声明
This site by Linest is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由Linest创作并维护的博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。