A Game of 2009 Cards


I got this problem from Rustan Leino, who got it from Radu Grigore. It may have been used as a problem in the 2009 Math Olympics.

I solved it and wrote up my solution.


There's a table with a row of 2009 cards. Each card has a red side and a blue side. We'll say that a card is red if the color on its visible face is red, and analogously for blue. Two players take turns making the following move: select any 50 consecutive cards where the left-most card is red, then flip each of those 50 cards (thus, for those 50 cards, turning red cards into blue cards and blue cards into red cards). Both players look at the cards from the same side of the table, so "left-most" means the same to both of the players. (That is, you can think of one end of the table as being designated as the left end.) When it's a player's turn, if that player can't make a move (that is, if there's no way to select 50 consecutive cards the left-most one of which is red), then that player loses and the other player wins. If you're one of the players and all cards are initially red, can you be sure to win, and if so, do you want to be the player who goes first or second?

Solution     Reveal