IMO Problem Shortlist

Question

Consider 2009 cards, each having one gold side and one black side, lying in parallel on a long table. Initially all cards show their gold sides. Two players, standing by the same long side of the table, play a game with alternating moves. Each move consists of choosing a block of 50 consecutive cards, the leftmost of which is showing gold, and turning them all over, so those which showed gold now show black and vice versa. The last player who can make a legal move wins. a. Does the game necessarily end? b. Does there exist a winning strategy for the starting player?

Accepted Answer

a. We interpret a card showing black as the digit

0

and a card showing gold as the digit

1

. Thus each position of the

2009

cards, read from left to right, corresponds bijectively to a nonnegative integer written in binary notation of

2009

digits, where leading zeros are allowed. Each move decreases this integer, so the game must end.

b. We show that there is no winning strategy for the starting player. We label the cards from right to left by

1, \dots, 2009

and consider the set

S

of cards with labels

50 i

,

i = 1, 2, \dots, 40

. Let

g_{n}

be the number of cards from

S

showing gold after

n

moves. Obviously,

g_{0} = 40

. Moreover,

∣ g_{n} - g_{n + 1} ∣ = 1

as long as the play goes on. Thus, after an odd number of moves, the nonstarting player finds a card from

S

showing gold and hence can make a move. Consequently, this player always wins.