Nim Game

数学

各种花式取石头~

巴什博奕

单堆，轮次限制

一堆石头个数为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
2
3
f(n) = true;
if(n1 > 0 && n2 > 0 && n1 != n2) f(n1,n2) = true;
//先手总是使得两堆相等，必然由对方先拿光一堆，退化到f(n)的局面

考虑每堆个数的二进制形式，每个数位上进行模2加法，如果各个数位的结果都是0，那么视为平衡态。模2加法等效于异或，即n1^n2^...^nm = 0。
如果初始状态是非平衡，那么先手任务是取一定量石头转化为平衡态，从而可以必胜。反之初始即平衡那么后手必胜。

证明：
引理1：平衡状态下，进行任何下一步操作将会打破平衡
引理2：非平衡状态下，总可以进行一步操作到达平衡状态
详细可参见维基百科

变形：
1.任何大于1的自然数都可以分解成质数的乘积，给定一个数两人轮流用质数的幂次去除，先得到1的获胜
例如720=24*32*51，问题转化为三堆石头分别为4,2,1

延伸
1.变更胜负条件，取最后一个石头的负
问题的重点是如何给对手留一个

1
2
3
4
5
f(1) = false;//别无选择，先手必败
if(n > 1) f(n) = true;//拿n-1个，给对方留一个，先手必胜
if(n > 0) f(1,n) = true; //先手把n全拿走，先手必胜
if(n1 > 1 && n2 > 1 && n1 != n2) f(n1,n2) = true;
//先手使得两堆相等，必然由对方破坏平衡，最终退化到上面f(1,n)和f(n)的局面

结论：有奇数个堆，并且每堆为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国际许可证。

本文永久链接：http://linest.github.io/2016/10/07/math-game-nim/