IMO 2004 SL C5

Origin: NZL | Category: Combinatorics

Problem

Let N be a positive integer. Two players A and B, taking turns, write numbers from the set {1, . . . , 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.

Solution

We say that a number n \in{1, 2, . . ., 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 n0 = N, ni+1 = [ni/2] for i = 0, 1, . . . and let k be such that nk = 1. Consider the sets Ai = {ni+1 + 1, . . . , ni}. We call a set Ai all-winning if all numbers from Ai 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 Ai is even-winning and consider Ai+1. Multiplying any num- ber from Ai+1 by 2 yields an even number from Ai, which is a losing number. Thus x \inAi+1 is winning if and only if x + 1 is losing, i.e., if and only if it is even. Hence Ai+1 is also even-winning. (ii) Suppose Ai is odd-winning. Then each k \inAi+1 is winning, since 2k is losing. Hence Ai+1 is all-winning. (iii) Suppose Ai is all-winning. Multiplying x \inAi+1 by two is then a losing move, so x is winning if and only if x+1 is losing. Since ni+1 is losing, Ai+1 is odd-winning if ni+1 is even and even-winning otherwise. We observe that A0 is even-winning if N is odd and odd-winning other- wise. Also, if some Ai is even-winning, then all Ai+1, Ai+2, . . . 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 A0, A1, . . . are alternately odd-winning and all- winning with A0 odd-winning, which is equivalent to N = n0, n2, n4, . . . 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 = 11111010100 in the binary system, 2004 is of type A. The least N > 2004 that is of type B is 100000000000 = 211 = 2048. Thus the answer to part (b) is 2048.