# A puzzle on game theory

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.

-
Are $1$ and $13$ allowed integers? – Macavity Aug 17 '13 at 19:51
@Macavity: The puzzle doesn't explicitly say anything about that. But I guess it is inclusive. – Mischelle Aug 17 '13 at 19:55
Depends how well Alice plays. It may be a good idea for Alice to lose every so often, in order to keep the sucker hooked. By the way, probably $1$ and $13$ are allowed. Doesn't chane things much either way. – André Nicolas Aug 17 '13 at 19:56
@Macavity: For this particular puzzle it's given $n = 1251$ and $k = 19$. But I am more interested in finding the general solution. – Mischelle Aug 17 '13 at 20:01
Alice wants, on her first move, to make the value $=1 \mod{14}$. Her strategy after this is to subtract $14-b_i$ where $b_i$ is Bob's $i$th move. When Alice eventually ends on exactly $1$, Bob has no choice but to push the value below $1$ and lose. – Dan Rust Aug 17 '13 at 20:03

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.

-
For $\bmod$ as a binary operator use \bmod. – Brian M. Scott Aug 18 '13 at 2:06

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.

-
Most of the time, when a problem in probability, statistics or game theory says "pick a number from $1$ to $13$" they mean inclusive. Certainly up for interpretation, but that's the most common usage. Would you really expect them to say "between $0$ and $14$? – Thomas Andrews Aug 17 '13 at 20:09
@MarkBennet The problem allows negative number results. "The game ends when n becomes less than 1." Says nothing about non-negative. – Thomas Andrews Aug 17 '13 at 20:09
@ThomasAndrews The OP guessed not inclusive. Besides this seemed more interesting a case, the other is quite similar and simpler... – Macavity Aug 17 '13 at 20:11
It's true that the OP guessed, but that doesn't mean OP guessed right, and it is usually right to make the guess you'd make. OP is, after all, seeking advice, and OP is only guessing - didn't say this interp was sure. – Thomas Andrews Aug 17 '13 at 20:12
@ThomasAndrews Thanks for that accurate reading - apologies for error. – Mark Bennet Aug 17 '13 at 20:13