Learn / Library / Brainteasers

Restricted chip taking

BrainteasersMedium

A pile has $20$ chips. $2$ players alternate, and on each move a player removes exactly $1$ , $3$ or $4$ chips; a move that needs more chips than remain is not allowed. The player who cannot move loses, so whoever takes the last chip wins. You move first and both players play optimally. How many chips must you remove on your first move to guarantee a win?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Label pile sizes from $0$ upward as won or lost for the player to move, and look for a repeating pattern.

Solution

Size $0$ is lost for the mover; sizes $1$ , $3$ and $4$ are won by taking everything, and size $2$ is lost because the only move leads to $1$ .
Continuing, sizes $5$ and $6$ are won, since they reach $2$ by removing $3$ or $4$ , while $7$ is lost because its moves lead to $6$ , $4$ and $3$ .
The pattern repeats with period $7$ : the lost sizes are those with remainder $0$ or $2$ on division by $7$ .
From $20$ the moves lead to $19$ , $17$ and $16$ , and only $16$ is lost, because $16 = 2 \times 7 + 2$ .
So you remove $4$ chips first.

Answer: $4$

Next question Back to the library