Maths Olympiad Prep

Library / /22 of 22

Combinatorics Difficulty 9.2 IMO level Prove it Germany

On a table, 2009 cards lie next to each other in a row. Initially, for all cards the top side is white and the bottom side is black. The cards are numbered from 11 to 20092009.

Two players AA and BB take turns making a move, with AA starting. Each move consists of the player choosing a card with number kk (k<1969k < 1969) whose white side is facing up, and then turning over the cards with numbers k,k+1,k+2,,k+40k, k+1, k+2, \ldots, k+40 in their places. The last player who was able to make a valid move wins the game.

a) Decide whether this game necessarily ends.

b) For which of the two players does a winning strategy exist?

Solution

a) If the game does not end, then, since there are at most 220082^{2008} different possible game states, there must exist a periodically repeating sequence of states. Let kk be the smallest number of the cards that are turned over within this period. However, to turn the card with number kk from black to white, a card with a number smaller than kk must be chosen – a contradiction to minimality! Therefore, the game must end after finitely many moves.

b) We consider the cards with numbers 41k41k, where 1k481 \leq k \leq 48. The highest of these cards, with number 19681968, is the last one that can be chosen. With each move, exactly one of these cards is turned over. Since the game ends when all cards up to number 19681968 are black, and since these cards are all white at the start, after every double move of AA and BB an even number of them is white again; thus BB always finds an odd number of white cards from this set and can therefore always move. Hence BB inevitably wins the game, no matter how he plays.

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: MathNet, licensed CC-BY-4.0. Statement translated into English from de; metadata (topic, difficulty) added by this project.