A puzzle on game theory

Question

Bob and Alice are playing a game. They will start with an integer $n$. Alice goes first, in each turn, a player can choose an integer between 1 and 13 and that number is to be subtracted from $n$. They will repeat this process alternatively. The game ends when $n$ becomes less than 1. The person who will be the telling the last number will lose the game.

Given $n$ (initial value), how could we determine the value of $n$ after the $k$th turn of Alice (If Alice plays optimally)?

PS: For this particular puzzle, it is given $n = 1251$ and $k = 19$. However, I am interested in the general solution.

Answer 1

Assuming only integers $\in \{2, 3, ... 12\}$ can be chosen for subtracting, clearly having $n$ of $1$ or $2$ is a bad position. It follows that $n \in \{3, 4, ...14\}$ is good, as this allows putting your opponent in a bad position at the next turn. Then $15, 16$ are bad positions, as you end up putting your opponent in a good position. Then again $\{17, 18, ... 28\}$ are all good. And so on and so forth...

So if Alice starts with a good $n$, she would subtract the required number to keep Bob bad. If Alice starts with a bad $n$, tough luck or hope Bob slips.

Answer 2

Given the strategy outlined in the comments,

• If $n\equiv1\pmod{14}$ then Alice can not win and so her strategy is essentially irrelevant so we can't tell what her $i$th move will be (however we can put bounds on it, given that Bob has a winning strategy).

• If $n\not\equiv 1\pmod{14}$ then Alice's first move will put the counter at $n-(n\bmod 14)+1$. Every subsequent move Alice makes after this will be $14$ less than her $1$st move and so her $i$th move will put the counter at $$n-(n\bmod 14)+1-14(i-1)=n-(n\bmod 14)-14i+15\;.$$

---

Working assumptions:

• Both players are perfectly rational and aim to win.

• Players can choose to reduce the current total by any element in the set $\{1,\ldots, 13\}$.

• If a player can not force a win then we can not give an algorithm for their strategy.

• Alice adopts the following strategy in the case that $n \not\equiv 1\pmod{14}$. On her first move, she makes the value of the counter $\equiv 1\pmod{14}$. Her strategy after this is to subtract $14−b_i$ where $b_i$ is the element that Bob has chosen to subtract from the counter on his $i$th move. When Alice eventually ends on exactly $1$, Bob has no choice but to push the value below $1$ and lose.