There are 2n cards labeled 1, 2, ..., 2n respectively, and the cards are distributed randomly between two players so that each has n cards. Each player takes turns to place one card, and you win if you put down a card so that the current sum of all the played cards is divisible by 2n+1.

For example, if n=10, and the previously placed cards are 5, 8, 9, 19, then if player A now places 1, he wins since 5+8+9+19+1 = 42 is divisible by 2*10+1=21.

Assuming both players want to win, what strategy should one adopt in order to win? Following the strategy, is there a consistent winner of this game?

(In reply to re(2): Solution by David Shin)

This sounds like the second question in the puzzle has been answered.  It confirms what playing through the tree structure by computer also says: that player 2 always has the win.

But the first question asks what the winning strategy is.  Obviously, if an immediate win is available, one should go for it.  Also, if an immediate win is not yet available, one should not play a card that allows the opponent an immediate win on the next turn.  But if there's more than one such play, which is to be used.

A simulation, using just the naive strategy of going for immediate wins and avoiding giving the opponent an immediate win, indicates that as n increases, the odds would start to favor the first player.  So there must be a strategy beyond this naive one.  Is the winning strategy something simpler than following a decision tree all the way to the end of the game?

Posted by Charlie on 2005-01-10 19:11:59