2004 ISL C5 wrote:

Let $N$ be a positive integer. Two players Alice and Bob take turns to write numbers from the set ${1, 2,... ,N}$ on a blackboard. Alice begins the game by writing $1$ on her first move. If a player has written $n$ on a certain move, the adversary is then allowed to write either $n + 1$ or $2n$ (provided the number does not exceed $N$ ). The player who writes $N$ wins. We say that $N$ is of type A or type B according to whether Alice or Bob has a winning strategy.

(a) Determine whether $N = 2004$ is of type A or type B.
(b) Find the least $N > 2004$ whose type is different from the type of 2004.

Solution

Tidbit