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.)
Question re(3): Solution | Comment 5 of 9 |
(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
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 (8)
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