# 2009 cards | combinatorics

Consider 2009 cards which are lying in sequence on a table. Initially, all cards have their top face white and bottom face black. The cards are enumerated from 1 to 2009. Two players, Amir and Ercole, make alternating moves, with Amir starting. Each move consists of a player choosing a card with the number k such that $k < 1969$ whose top face is white, and then this player turns all cards at positions $k,k+1,\ldots,k+40$. 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?

-
This is an impartial game like Nim, where the moves available are the same for both players. The Sprague-Grundy theorem, en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem is your friend. –  Ross Millikan Aug 29 '11 at 12:43
@Ross: I don't see how that brings us any closer to solving (b). The theorem tells us that every position is equivalent to a nimber, but actually finding those nimbers is at least as difficult as finding the game values of the positions, no? –  joriki Aug 29 '11 at 13:57
@joriki: in the theorem it describes how to find the value of a position as the minimum excluded value. But yes, it can be a lot of work in a big tree. I hoped that thought down that line would (and the IMO suggester probably thought it should) bring the answer. –  Ross Millikan Aug 29 '11 at 14:24
@Ross: It's probably helpful to think along those lines, but for the concrete work of finding the game value (which is what (b) asks) it seems like a complication -- you have to traverse the same tree as you would for the game value, just that instead of working out a $0$ or a $1$ based on $0$s and $1$s you work out nimbers based on nimbers, though in the end unless you want to combine the game with some other game all you're interested in is whether these are $0$ or not... –  joriki Aug 29 '11 at 14:31
What is the purpose of card number 2009? –  Christian Blatter Aug 29 '11 at 15:20

There is a solution on page 780 of Dusan Djukic, Vladimir Jankovic, Ivan Matic, Nikola Petrovic, The IMO Compendium; A Collection of Problems Suggested for The International Mathematical Olympiads, 1959-2009, which I found on Google Books.

-

It would be worth telling us what you have tried.

Some hints:

• Are there are a finite number of possible positions (and if so what is an upper bound)?

• Can there be a cycle of positions (consider the card with the smallest number turned over)?

• Will the starting player have a winning strategy if initially there are only 41 cards? 42? etc?

-
Actually, I think the first non-trivial number of cards is 82. (Or maybe 83, depending on what you consider trivial.) –  Ilmari Karonen Aug 29 '11 at 11:46
@Ilmari: I think you mean $82$. Each turn turns over $41$ cards. –  joriki Aug 29 '11 at 11:48
@joriki: Thanks, corrected. –  Ilmari Karonen Aug 29 '11 at 11:51