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) |
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 |
