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) |
3 coins, 4 coins, and a question
|
 | Comment 2 of 5 |  |
If 3 coins, a greedy strategy applies. Number the coins 1, 2 and 3. Each player takes the biggest coin on either end. Player 1 wins if the sum of the odd coins (1 and 3) is greater than the even coin (2). Player 2 wins if the even coin is greater than the sum of the odd coins.
Examples:
3-5-4 player 1 wins, 7 to 5
1-5-3 player 2 wins, 5 to 4
1-2-1 tie
/*********************/
But things get complicated quickly. If 4 coins, a greedy strategy no longer works. Number the coins 1 through 4. Player 1 can guarantee a win by taking coin 1 if the sum of the odd coins is greater than the sum of the even coins, and by taking coin 4 if the sum of the even coins is greater, and by taking the largest available coin if they are tied.
Examples, using this winning strategy.
1-2-5-3 Player 1 takes coin 1, and wins 6 to 5
6-5-3-5 Player 4 takes coin 4, and wins 10 to 9
But this last example raises a question of what our objective is. If the objective is just to have the larger amount (which is what the problem asks for), then that is a winning strategy. But it is not necessarily the way to have the largest possible amount.
If the coins are
6-5-3-5, then the largest amount is achieved if player 1 takes the 6 first, thus winning 11 to 8, even though it runs counter to our stated winning strategy.
It seems to me that the a description of the strategy which maximizes the bounty is not simple.
BUT, WHICH STRATEGY ARE WE ASKED FOR? Clearly, a strategy which maximizes the bounty is a winning strategy. But there are other strategies that are simpler to express which are also winning strategies, if the objective is just to have more than the opponent.
| Posted by Steve Herman on 2015-11-27 18:35:49 |
