Learn / Library / Brainteasers

Which starts to avoid

BrainteasersMedium

In a game for $2$ players, a pile starts with $n$ beads. Players alternate, and each move removes exactly $2$ or exactly $5$ beads; a move that needs more beads than remain is not allowed. A player who cannot move loses. Both players play optimally. For how many starting values of $n$ from $1$ to $50$ does the second player win?

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

Hint

Classify small piles as won or lost for the player to move until the pattern repeats.

Solution

Piles of $0$ and $1$ are lost for the mover, since no move is possible.
Piles of $2$ and $3$ are won by moving to $0$ or $1$ , pile $4$ is lost because it only reaches $2$ , and piles $5$ and $6$ are won by reaching $0$ or $4$ .
From then on the pattern repeats with period $7$ , so the lost piles are those with remainder $0$ , $1$ or $4$ on division by $7$ .
From $1$ to $50$ there are $7$ values with remainder $0$ , $8$ with remainder $1$ and $7$ with remainder $4$ .
So the second player wins for $7 + 8 + 7 = 22$ starting values, and the answer is $22$ .

Answer: $22$

Next question Back to the library