xxxiii. Bachet's Game and the 21 Game

Problem. A pile of $n$ stones; players alternately take $\mathrm{1..}k$ stones; whoever takes the last stone wins. (The “21 game” is $k=3$, $n=21$ in reverse form.)

Answer: the first player loses iff $n\equiv 0(\mathrm{mod}k+1)$; the winning move is to take $n\mathrm{mod}(k+1)$ stones.

bool bachetFirstWins(long long n, long long k) { return n % (k + 1) != 0; }    // take 1..k, last stone wins

Variant	Losing positions
misère (taking the last stone loses)	$n\equiv 1(\mathrm{mod}k+1)$
allowed moves form a set $S$	compute win/lose by DP; the pattern is eventually periodic
several piles	Grundy value $n\mathrm{mod}(k+1)$ per pile, XOR them (Sprague–Grundy)

Proof: multiples of k + 1 lose

From a multiple of $k+1$, any move takes $\mathrm{1..}k$ stones and leaves a non-multiple. From a non-multiple, taking $n\mathrm{mod}(k+1)\in [1,k]$ stones leaves a multiple. Position $0$ is a loss for the player to move. By induction, multiples of $k+1$ are losing and all others winning. Checked against the game DP for $k\le 6$, $n<60$.