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 \( 2n \) (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-winning 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 \( 2k \) is losing. Hence \( 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 even-winning 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 all-winning 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{100000000000} = 2^{11} = 2048 \). Thus the answer to part (b) is 2048.