NOTE & BLOG

Problem Citation

A pile of stones, two people take turns to take at least 1 stone and at most 2 stones. Whoever gets the last stone loses. Is there a sure-win strategy of playing first and playing second? That's a famous Bash Game Problem

Analysis

There is a pile of n items in total, and two players take turns picking up items from it. It is stipulated that each time at least one item must be taken, and at most m items can be taken. The one who takes the last item wins.

Let

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

$\quad (\text{i})\quad$If $r=0$, the second player will win. The strategy is as follows:

If the first player takes away $k$ items, the second player takes away $m+1-k$ items. The result is $(m+1)(q-1)$ items left. By maintaining this method, the second player will win.

$\quad (\text{ii})\quad$If $r≠0$, the first player will win. The strategy is as follows:

The first player takes away $r$ items first. If the second player takes away $k$ items, the first player takes away $m+1-k$ items. The result is $(m+1)(q-1)$ items left. By maintaining this method, the first player will win.

In short, to ensure that the opponent is left with a multiple of $(m+1)$, one can eventually win.

Extension

If it is stipulated that the one who takes the last item loses, let

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

$\quad (\text{i})\quad$If $r=0$, the second player will win. The strategy is as follows: If the first player takes away $k$ items, the second player takes away $m+1-k$ items. The result is $(m+1)(q-1)+1$ item left. By maintaining this method, the first player will take the last item.

$\quad (\text{ii})\quad$If $r≠0$, the first player will win. The strategy is as follows: The first player takes away $r$ items first. If the second player takes away $k$ items, the first player takes away $m+1-k$ items. The result is $(m+1)(q-1)+1$ item left. By maintaining this method, the second player will take the last item.

Mini Game

Two people take turns counting, each time reporting at least one, at most ten. Whoever reaches $100$ first wins.

Attached code:

#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("first\n");
        else printf("second\n");
    }
    return 0;
}

References:

• [1] Summary of Bash Game
• [2] Bash Game hdu 1846
• [3] Bash Game - Baidu Baike