All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Who will win? (Posted on 2005-01-10)
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?

 See The Solution Submitted by Bon Rating: 2.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 More thorough solution | Comment 7 of 9 |

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 S1, S2, ..., Sk+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 Si and Sj such that the same move x for Player 1 gives him the win.  Thus,

Si+x = Sj+x (mod 2n+1)

or

Si = Sj (mod 2n+1),

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

 Search: Search body:
Forums (0)