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?

It seems my first solution was too brief.  Here's a more thorough version:

To show that Player 2 will win, it suffices to show that he can always make a move that prevents Player 1 from winning on the very next turn.  The reason is that if he continues to do this until the end of the game, his very last move will win him the game.  Otherwise, he will have won at some earlier point in the game.

Now, suppose it is Player 2's turn, and that he has (k+1) numbers to choose from.  Player 1 will have k numbers to choose from on his next turn.  This means that Player 2 can induce one of (k+1) possible distinct sums S₁, S₂, ..., S_k+1 for Player 1's next turn.  Suppose for sake of contradiction that each of these leads to an immediate win for Player 1.  By the Pigeonhole Principle, there are two distinct sums S_i and S_j such that the same move x for Player 1 gives him the win.  Thus,

S_i+x = S_j+x (mod 2n+1)

or

S_i = S_j (mod 2n+1),

a contradiction. 

Posted by David Shin on 2005-01-10 19:50:27