Counting Game to 200
You and a friend take turns picking numbers. The first player starts by choosing any integer from $1$ to $8$. After that, each player on their turn adds between $1$ and $8$ to the running total. Whoever is the player that makes the total hit exactly $200$ wins.
Both players play optimally. You go first. What number should you pick on your first turn to guarantee a win?
Hints
- Think backwards from $200$. What position would you need to be at so that no matter what your opponent does, you can reach $200$ on your next turn?
- Notice that each turn advances the total by $1$ to $8$, and $1 + 8 = 9$. How can you use the fact that you can always "complement" your opponent's move to $9$?
- Compute $200 \bmod 9$. The remainder tells you what the first player should pick to land on the sequence of winning milestones.
Worked Solution
How to Think About It: Work backwards from the goal. If you can say $200$, you win. So the question becomes: what positions guarantee you can say $200$ on your next turn? If the total is at $191$, then no matter what your opponent adds (1 through 8), the total lands in $192$-$199$ -- and you can always bump it to exactly $200$. So $191$ is a winning position for whoever says it. The same logic applies recursively: to guarantee you can say $191$, you need to be the one who says $182$, then $173$, $164$, and so on. Each "safe" position is $9$ less than the next. You start to see the pattern -- the key positions are all congruent to $200 \bmod 9$.
Quick Estimate: The step size on each turn is $1$ to $8$, so the combined move of you plus your opponent spans $2$ to $16$, but the critical observation is that $1 + 8 = 9$. Whatever your opponent adds (call it $x$), you can respond with $9 - x$, advancing the total by exactly $9$ every two turns. Since $200 = 9 \times 22 + 2$, you need $22$ full rounds of $9$ after your opening move. That opening move must be $2$.
Approach: Use backward induction and modular arithmetic.
Formal Solution:
Define a position as the current running total. A position $s$ is a *winning position* for the player whose turn it is if they can force a win from $s$.
- From position $s$, the current player can move to any total in $\{s+1, s+2, \ldots, s+8\}$.
- The current player wins immediately if they can reach $200$, i.e., if $200 - s \leq 8$ and $200 - s \geq 1$, meaning $s \in \{192, 193, \ldots, 199\}$.
- If you land on $s = 191$, the opponent is forced into $\{192, \ldots, 199\}$. Then on your next turn you pick $200$ and win. So $191$ is a winning position for the player who says it.
More generally, define the set of "winning milestones" as: $$W = \{200, 191, 182, 173, 164, \ldots, 11, 2\}$$ which is $\{200 - 9k : k = 0, 1, 2, \ldots, 22\}$, or equivalently all values congruent to $2 \pmod{9}$.
The strategy: always move to the next value in $W$. If you are at some $w \in W$ and your opponent adds $x$ (where $1 \leq x \leq 8$), you add $9 - x$ to reach $w + 9$, the next milestone. Since $1 \leq 9 - x \leq 8$, this is always a legal move.
The first milestone is $2$, which is in the range $\{1, \ldots, 8\}$, so the first player can reach it on the opening move.
Answer: Pick $2$ on your first turn, then always respond with $9 - x$ where $x$ is your opponent's move. This locks you onto the sequence $2, 11, 20, 29, \ldots, 182, 191, 200$ and guarantees you say $200$.
Intuition
This is the classic "Nim-like" counting game, and the underlying principle is modular arithmetic as a strategy tool. The reason the number $9$ controls everything is that each player picks from $1$ to $8$, so the sum of any two consecutive moves (yours and your opponent's) can always be forced to equal $9$ by the player who moves second in that pair. Once you land on a number congruent to $200 \bmod 9$, you have a "mirror strategy" -- whatever your opponent does, you complement it to $9$, marching toward $200$ in lockstep.
This pattern generalizes immediately: in any "race to $N$" game where each turn you can add $1$ to $k$, the first player wins if and only if $N \bmod (k+1) \neq 0$, and the winning first move is $N \bmod (k+1)$. If $N \bmod (k+1) = 0$, the second player has the winning strategy. In quant interviews, this type of problem tests whether you can identify the recursive structure, reduce it to a simple invariant, and state the full strategy cleanly -- skills that directly transfer to thinking about dynamic hedging, optimal execution, and any sequential decision problem.