12. C5 (NZL) Let $N$ be a positive integer. Two players $A$ and $B$, taking turns, write numbers from the set $\{1, \ldots, N\}$ on a blackboard. $A$ begins the game by writing 1 on his first move. Then, if a player has written $n$ on a certain move, his adversary is allowed to write $n+1$ or $2 n$ (provided the number he writes does not exceed $N$ ). The player who writes $N$ wins. We say that $N$ is of type $A$ or of type $B$ according as $A$ or $B$ has a winning strategy.
(a) Determine whether $N=2004$ is of type $A$ or of type $B$.
(b) Find the least $N>2004$ whose type is different from that of 2004 .
12. We say that a number $n \in\{1,2, \ldots, N\}$ is winning if the player who is on turn has a winning strategy, and losing otherwise. The game is of type $A$ if and only if 1 is a losing number.
Let us define $n_{0}=N, n_{i+1}=\left[n_{i} / 2\right]$ for $i=0,1, \ldots$ and let $k$ be such that $n_{k}=1$. Consider the sets $A_{i}=\left\{n_{i+1}+1, \ldots, n_{i}\right\}$. We call a set $A_{i}$ all-winning if all numbers from $A_{i}$ are winning, even-winning if even numbers are winning and odd are losing, and odd-urinning if odd numbers are winning and even are losing.
(i) Suppose $A_{i}$ is even-winning and consider $A_{i+1}$. Multiplying any number from $A_{i+1}$ by 2 yields an even number from $A_{i}$, which is a losing number. Thus $x \in A_{i+1}$ is winning if and only if $x+1$ is losing, i.e., if and only if it is even. Hence $A_{i+1}$ is also even-winning.
(ii) Suppose $A_{i}$ is odd-winning. Then each $k \in A_{i+1}$ is winning, since $2 k$ is losing. Hence $\mathcal{A}_{i+1}$ is all-winning.
(iii) Suppose $A_{i}$ is all-winning. Multiplying $x \in A_{i+1}$ by two is then a losing move, so $x$ is winning if and only if $x+1$ is losing. Since $n_{i+1}$ is losing, $A_{i+1}$ is odd-winning if $n_{i+1}$ is even and even-winning otherwise. We observe that $A_{0}$ is even-winning if $N$ is odd and odd-winning otherwise. Also, if some $A_{i}$ is even-winning, then all $A_{i+1}, A_{i+2}, \ldots$ are evenwinning and thus 1 is losing; i.e., the game is of type $A$. The game is of type $B$ if and only if the sets $A_{0}, A_{1}, \ldots$ are alternately odd-winning and allwinning with $A_{0}$ odd-winning, which is equivalent to $N=n_{0}, n_{2}, n_{4}, \ldots$ all being even. Thus $N$ is of type $B$ if and only if all digits at the odd positions in the binary representation of $N$ are zeros.
Since $2004=\overline{11111010100}$ in the binary system, 2004 is of type $A$. The least $N>2004$ that is of type $B$ is $\overline{1000000000000}=2^{11}=2048$. Thus the answer to part (b) is 2048 .