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.)
 re: More thorough solution Comment 9 of 9 |
(In reply to More thorough solution by David Shin)

So in less-math speak:

Since the numbers on the cards are all less than the multiplier there is only ever one possible card that when played will cause an immediate win (for example if you only have cards up to ten, if the current sum is 10, it may be possible to make ten, but there's no way to make 22: the most you can get is 20.  You would have to play a one to make 11).  Now on your turn either you have that card and you play it and do a little victory dance, or you don't.  If you don't have it, then you try to play a card such that your opponent can't win on the next term.

Now consider the progress of a game.  On player one's turn looks through his cards, sees what he has and what he's missing (these are the cards p2 has) and plays a card that he has the equals-2n+1-match card to.  Since there is not a 2n+1 card p2 cannot win on the first round: the most he can make is 2n.  Player 1 now has n - 1 cards left in his hand and it is Player 2's turn.  Player 2 now has n cards still in his hand.  Since each of his cards contains a different number, each possible play requires a specific card from player 1 on his next turn if p1 is to win.  However, since player 2 has one more card than player 1, p1 cannot have the unique matches to every card in player 2's hand, so player 2 has at least  one card he can play so player 1 cannot win next round.  Note that he might have more than one possible play, but it doesn't matter which one he takes.  During his turn, player 2 will always have one more card than player 1, and thus will always have a move which player 1 cannot match.  Thus, in the worst case, player 2 will have to play all his cards and win on the last hand.

The best case for player 2 is when player 1 draws all even or all the odd cards.  In this case p1 has no moves to stymie p2 on his first move, so player 2 wins in round 1.

...which leads us to an intersting follow up question - there are two possible deals which can lead to a perfect player 2 beating a perfect player 1 after one round.  What is the expected length of a game with 2n card?

I'm new to this site, so let me know if posting interesting follow up question is against the rules, or gauche, or both.

 Posted by Jay Schamel on 2005-01-14 23:49:40

 Search: Search body:
Forums (0)