巴什博奕

组合算法 ACM

---

简单巴什博弈

巴什博奕(Bash Game)：有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。

显然，如果$n=m+1$，那么由于一次最多只能取$m$个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果

$$n=(m+1)r+s \\ r\in \mathbb{N},1\le s\le m$$
那么先取者要拿走$s$个物品，如果后取者拿走$k\in{1\cdots m}$个，那么先取者再拿走$m+1-k$个，结果剩下$(m+1)(r-1)$个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下$(m+1)$的倍数，就能最后获胜。

对于巴什博奕，如果我们规定最后取光者输，那么又会如何呢？
$(n-1)\mod(m+1)\ne 0$则先手胜利。

推广的巴什博奕

同样是n个物品，两个人轮流从这堆物品中取物，但规定每次至少取$p$个，最多取$q$个。最后取光者得胜。（其中$q\geq p$）
1. 当$n=0$时，先取者输。
2. 当$0\leq(n-1)\mod(p+q)\lt q$时，则先取者赢。
3. 当$q\leq(n-1)\mod(p+q)\lt p+q$,时，则先取者输。

为了避免公式中出现对负数取模的另一个方法：
1. 当$0\leq(n+p+q-1)\mod(p+q)\lt q$时，则先取者赢。
2. 当$q\leq(n+p+q-1)\mod(p+q)\lt p+q$时，则先取者输。

如果我们规定最后取光者输，那么又会如何呢？
1. 规定当$n=0$时，先取者赢。
2. 当$0\leq(n-1)\mod(p+q)\lt p$时，则先取者输。
3. 当$p\leq(n-1)\mod(p+q)\lt p+q$时，则先取者赢。