Maths Olympiad Prep

Library / /307 of 520

Combinatorics Difficulty 6.6 National olympiad Prove it

NZL 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?

Solution

(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,,20091, \ldots, 2009 and consider the set SS of cards with labels 50i,i=1,2,,4050 i, i=1,2, \ldots, 40. Let gng_{n} be the number of cards from SS showing gold after nn moves. Obviously, g0=40g_{0}=40. Moreover, gngn+1=1\left|g_{n}-g_{n+1}\right|=1 as long as the play goes on. Thus, after an odd number of moves, the nonstarting player finds a card from SS showing gold and hence can make a move. Consequently, this player always wins.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.