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

Home > Games
Coin contest (Posted on 2015-11-27) Difficulty: 3 of 5
The coins of various denominations are arranged in a chain (e.g., a row, a semicircle) with two "end points" and the others each having two neighbors.
A move consists in removing an end coin, whereby the coin's immediate (and the only) neighbor becomes naturally an end coin available for the removal on one of the successive moves.
The players take turns, 1st defined randomly.
When all the coins have been removed, the game ends, and the players count their bounties. The player with the larger amount wins.

Devise a winning strategy for one of the players.

No Solution Yet Submitted by Ady TZIDON    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution If you have a hammer, every problem looks like a nail | Comment 4 of 5 |
In the solution to my "Optimizing Potency" problem, which I just posted 2 days ago, I explained how that problem could be solved using what back in the day was referred to in my Operations Research class as "Dynamic Programming". Specifically, we approached that as a "Stagecoach Problem", solving the problem first for all of the possible end cases, and working backwards one stage at a time to the starting case. This approach reduces a problem that requires exponential time to solve to a problem that only requires polynomial (geometric) time.

And here it is again.  I do not believe that Ady's innocent problem has any closed form solution.  I think it requires an analysis of all possible moves or positions.  Of course, I could be wrong.

If there are n coins on the chain, then there are 2^(n-1) possible combinations of player moves.  One could walk a tree of all possible moves, to find at every point the "Best Move" which optimizes the final bounty.  The time required to do this increases exponentially with n.

Or, treating this as a stagecoach problem, one could evaluate the n one-coin positions, and then the (n-1) two-coin positions, ..., and eventually the 1 n-coin position.  This involves n(n+1)/2 evaluations, and only increases geometrically with n.

So, for instance, consider my last example of 6 5 3 5.  The stagecoach solution is as follows:
Position  Best Move  Leaving You get He Gets
--------  ---------  ------- ------- ---------
6         6          nothing 6       0
5         5          nothing 5       0
3         3          nothing 3       0
5         5          nothing 5       0
65        6          5       6+0=6   5 
53        5          3       5+0=5   3
35        5          3       5+0=5   3
653       6          53      6+3=9   5  
535       5          53      5+3=8   5
6535      6          535     6+5=11  8
The optimum 4-coin move is evaluated by looking at the two 3-coin positions in the table.
If you take the 6 coin, you leave a 535, which eventually gives you another 5 and the other player another 8.
If you take the 5 coin, you leave a 653, which eventually gives you another 5 and the other player another 9.
Taking the 6 therefore maximizes the bounty, because 6+5 is greater than 5+5.

  Posted by Steve Herman on 2015-11-28 08:47:11
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