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 and consider the set of cards with labels . Let be the number of cards from showing gold after moves. Obviously, . Moreover, as long as the play goes on. Thus, after an odd number of moves, the nonstarting player finds a card from showing gold and hence can make a move. Consequently, this player always wins.