Skip to content
Lex Blog

巴什博弈

一堆石子，两人轮流取，至少取 1 颗、至多取 2 颗，取到最后一颗石子的人输。

问题引入

一堆石子，两人轮流取，至少取 1 颗、至多取 2 颗，取到最后一颗石子的人输。先手与后手是否存在必胜策略？这就是著名的巴什博弈问题。

分析

设共有 n 个物品，两名玩家轮流从中取走物品。规定每次至少取 1 个，至多取 m 个，取走最后一个物品的人获胜。

设

n=(m+1)q+r(0≤r≤m)n=(m+1)q+r \quad( 0\leq r \leq m ) \\

(i)\quad (\text{i})\quad 若 r=0r=0，后手必胜。策略如下：

若先手取走 kk 个，后手就取走 m+1−km+1-k 个。结果剩下 (m+1)(q−1)(m+1)(q-1) 个。坚持此法，后手必胜。

(ii)\quad (\text{ii})\quad 若 r≠0r≠0，先手必胜。策略如下：

先手先取走 rr 个。若后手取走 kk 个，先手就取走 m+1−km+1-k 个。结果剩下 (m+1)(q−1)(m+1)(q-1) 个。坚持此法，先手必胜。

简而言之，只要保证留给对方的是 (m+1)(m+1) 的倍数，最终就能获胜。

扩展

若规定取走最后一个物品的人输，设

n−1=(m+1)q+r(0≤r≤m)n-1=(m+1)q+r \quad( 0≤r≤m ) \\

(i)\quad (\text{i})\quad 若 r=0r=0，后手必胜。策略如下：若先手取走 kk 个，后手就取走 m+1−km+1-k 个。结果剩下 (m+1)(q−1)+1(m+1)(q-1)+1 个。坚持此法，最终先手会取走最后一个物品。

(ii)\quad (\text{ii})\quad 若 r≠0r≠0，先手必胜。策略如下：先手先取走 rr 个。若后手取走 kk 个，先手就取走 m+1−km+1-k 个。结果剩下 (m+1)(q−1)+1(m+1)(q-1)+1 个。坚持此法，最终后手会取走最后一个物品。

小游戏

两人轮流报数，每次至少报 1 个、至多报 10 个，先报到 100100 的人获胜。

附上代码：

#include<cstdio>
#include<string.h>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(n%(m+1)) printf("先手\n");
        else printf("后手\n");
    }
    return 0;
}

参考资料：