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

Home > Games
Who will win? (Posted on 2005-01-10) Difficulty: 4 of 5
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),

a contradiction. 


  Posted by David Shin on 2005-01-10 19:50:27
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information