HMMT November, 2019

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:

Two players play a game, starting with a pile of $N$ tokens. On each player's turn, they must remove $2^{n}$ tokens from the pile for some nonnegative integer $n$ . If a player cannot make a move, they lose. For how many $N$ between 1 and 2019 (inclusive) does the first player have a winning strategy?

Solution

Solution:

The first player has a winning strategy if and only if $N$ is not a multiple of 3. We show this by induction on $N$ . If $N=0$ , then the first player loses.

If $N$ is a multiple of 3, then $N-2^{n}$ is never a multiple of 3 for any $n$ , so the second player has a winning strategy.

If $N$ is not a multiple of 3, the first player can remove either 1 or 2 coins to get the number of coins in the pile down to a multiple of 3, so the first player will always win.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.