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?

  • 2
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Aug 29 '11 at 12:43
  • $\begingroup$ @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? $\endgroup$ – joriki Aug 29 '11 at 13:57
  • $\begingroup$ @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. $\endgroup$ – Ross Millikan Aug 29 '11 at 14:24
  • $\begingroup$ @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... $\endgroup$ – joriki Aug 29 '11 at 14:31
  • 1
    $\begingroup$ What is the purpose of card number 2009? $\endgroup$ – 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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.