『算法-ACM 竞赛-数学』博弈论-巴什博奕（BashGame）

数学–博弈论–巴什博奕（Bash Game）

终于也轮到我做游戏了，他们做了好几个月的游戏了。

巴什博弈：

两个人做游戏，取石子，一个人最多可以可以取 M 个，至少取 1 个，最后取完的赢。

显然，如果 n=m+1，那么由于一次最多只能取 m 个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果 n=（m+1）r+s，（r 为任意自然数，s≤m),那么先取者要拿走 s 个物品，如果后取者拿走 k（≤m)个，那么先取者再拿走 m+1-k 个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。

举例 1：先手必胜（如果是傻子就好说了）

终结数 30 ，最大可以取 3 个，最少取 1 个

经过上面的公式推算- 3+1=4（m+1）

正常人：

如果先手足够聪明，那么他一定会胜利，他可以保证每次留给你剩下的数都是 4 的倍数 取 2 留 28，取 6 留 24，取 10 留 20，取 14 留 16，取 18 留 12，取 22 留 8，取 26 留 4，先手只要取到这些点必输。

康宝斌：

如过先手不够聪明，留给后手反击的机会，后者就可以通过先手的失误，先达到上面的点。

总结 谁先给对手留（m+1）倍数的数，谁就先胜利

一个人拿 1 ～ m 个，那谁面对 m+1 的局势的的时候则必败。假设 n=k*(m+1)+s,(k 为任意，s<m+1)，那我（先手）先把那个 s 个拿掉，然后让另一个人拿，从现在开始，只要我每次拿的个数与前面一个人拿的个数和等于 m+1,这样后拿的必定面对必败局势，即到最后另一个人拿完后肯定是剩 t(t<m)个给我，那就是我赢。

举例 2：先手必输

我们考虑这种情况：

终结数 20 ，最大可以取 3 个，最少取 1 个。

无论我去多少个，我不能留给我对手 K（M+1）个，这样的后果是，我会面对 K（M+1）的情况，也就是我必输。

总结：

那我们讨论一下什么时候必输，什么时候必赢。

当我一开始就面对 K（M+1)的局势，相当于对面给我制造了 K（M+1）的局势，而我是先手。

所以判断终止数%（M+1）=0？来判断先手必输，还是必赢。