Chip-Taking Game Optimal Strategy

Game Theory · Medium · Free problem

You and a friend are playing a game with 12 poker chips. You take turns, and on each turn you must pick up either 1 or 2 chips. The player who picks up the last chip loses.

  1. What is the optimal strategy? Would you rather go first or second?
  1. What if there were 150 chips instead?

Hints

  1. Think backward from the endgame. If 1 chip remains on your turn you lose -- classify small positions as winning or losing and look for a pattern.
  2. The losing positions follow a modular arithmetic pattern. Check which residue class mod 3 characterizes positions where every available move hands your opponent a win.
  3. The losing positions are exactly $n \equiv 1 \pmod{3}$. Your winning strategy is to leave such a count after every move -- if your opponent takes $x$, respond with $3 - x$.

Worked Solution

How to Think About It: This is a classic misere Nim-type game. The key question is: can you force your opponent into a losing position? Start from the end and work backward. If there is 1 chip left and it is your turn, you lose (you must take it). If there are 2 or 3 chips left and it is your turn, you win (take 1 or 2 to leave your opponent with exactly 1). If there are 4 chips left and it is your turn, you are stuck -- whether you take 1 or 2, your opponent lands on 2 or 3 and wins. So 4 is a losing position.

Setup: We classify each position as $L$ (losing for the player to move) or $W$ (winning). Backward analysis on small cases:

  • $n = 1$: must take the last chip. $L$.
  • $n = 2$: take 1, leave 1 for opponent. $W$.
  • $n = 3$: take 2, leave 1 for opponent. $W$.
  • $n = 4$: take 1 $\to$ 3 ($W$ for opponent), take 2 $\to$ 2 ($W$ for opponent). Both moves give opponent a winning position. $L$.
  • $n = 5$: take 1 $\to$ 4 ($L$ for opponent). $W$.
  • $n = 6$: take 2 $\to$ 4 ($L$ for opponent). $W$.
  • $n = 7$: take 1 $\to$ 6 ($W$ for opponent), take 2 $\to$ 5 ($W$ for opponent). $L$.

The pattern is clear: losing positions are

, 4, 7, 10, 13, \ldots$ -- precisely the values $n \equiv 1 \pmod{3}$.

Proof by Induction: Suppose all positions up to $n - 1$ are correctly classified.

  • If $n \equiv 1 \pmod{3}$: taking 1 leaves $n - 1 \equiv 0 \pmod{3}$ ($W$ for opponent), and taking 2 leaves $n - 2 \equiv 2 \pmod{3}$ ($W$ for opponent). Every move leads to a $W$ position for the opponent, so $n$ is $L$.
  • If $n \equiv 2 \pmod{3}$: taking 1 leaves $n - 1 \equiv 1 \pmod{3}$ ($L$ for opponent). There exists a move to a losing position, so $n$ is $W$.
  • If $n \equiv 0 \pmod{3}$: taking 2 leaves $n - 2 \equiv 1 \pmod{3}$ ($L$ for opponent). There exists a move to a losing position, so $n$ is $W$.

Part 1 -- 12 chips:

2 \equiv 0 \pmod{3}$, so this is a $W$ position. Go first. Take 2 chips immediately, leaving 10 ($\equiv 1 \pmod{3}$, losing for your opponent). Then on every subsequent turn, if your opponent takes $x$ chips, you take $3 - x$ chips. This maintains the invariant that after your turn the remaining count $\equiv 1 \pmod{3}$.

The game proceeds:

2 \to 10 \to 7 \to 4 \to 1$. When 1 chip remains it is your opponent's turn, and they must take it. You win.

Part 2 -- 150 chips:

50 \equiv 0 \pmod{3}$, same structure. Go first, take 2 chips to leave 148 ($\equiv 1 \pmod{3}$), then mirror with $3 - x$ on every turn.

General Rule: For $n$ chips:

  • If $n \equiv 1 \pmod{3}$: go second. Your opponent is in the losing seat.
  • If $n \equiv 0 \pmod{3}$: go first, take 2.
  • If $n \equiv 2 \pmod{3}$: go first, take 1.

In every winning case the strategy is identical: leave a count $\equiv 1 \pmod{3}$ after your move, then always take $3 - x$ where $x$ is what your opponent took.

Answer: For 12 chips, go first and take 2. For 150 chips, go first and take 2. Maintain the invariant of leaving $3k + 1$ chips after your turn by taking $3 - x$ whenever your opponent takes $x$. A position is losing for the player to move if and only if $n \equiv 1 \pmod{3}$.

Intuition

This is a textbook example of a Nim-variant (specifically a Bash game). The core principle is that when two players can each remove 1 to $k$ objects per turn, the game's structure repeats with period $k + 1$. Here $k = 2$, so the period is 3, and the losing positions form an arithmetic progression modulo 3. The misere condition (last chip loses rather than wins) shifts the losing positions by 1 compared to normal play, but the modular structure is identical. Once you see this, the entire game collapses to a single modular arithmetic check.

This pattern shows up constantly in combinatorial game theory and in puzzle-style interview questions. The broader lesson is backward induction -- start from terminal states and propagate values backward. It is the same principle behind dynamic programming, option pricing on trees, and optimal stopping. Interviewers love these problems because they test whether you can identify invariants and think recursively rather than trying to brute-force enumerate all possible games.

Open the full interactive solver →