superprismatic Posted August 11, 2011 Report Share Posted August 11, 2011 Here is a two-player game in which the players alternate turns: 100 coins of varying denominations are placed in a single row on a table. A player, during his turn, may take only one coin from either end of the row. Can either the first or second player guarantee that they can accumulate at least half of the value of all the coins? If not, why not? If so, how? Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 11, 2011 Report Share Posted August 11, 2011 Can values be duplicated (e.g 99 coins worth 1, and 1 coin worth 2)? Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 11, 2011 Author Report Share Posted August 11, 2011 Can values be duplicated (e.g 99 coins worth 1, and 1 coin worth 2)? Yes! Could even be weird like this: 12 coins worth 6.12 each, 16 coins worth 51 each, 57 coins worth .125 each , 14 coins worth 24 each, 1 coin worth 25. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 11, 2011 Report Share Posted August 11, 2011 (edited) Then the answer is no: all coins could be worth 1, and there would be no way to ever win (both players would always end up with half the pot) Edited August 11, 2011 by kevink Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 11, 2011 Author Report Share Posted August 11, 2011 Then the answer is no: all coins could be worth 1, and there would be no way to ever win (both players would always end up with half the pot) To win, one of them has to get at least half the value -- not more than half. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 11, 2011 Report Share Posted August 11, 2011 First player must always win. If coins of equal value, then first player always reaches half first. In other scenarios, For quick explanation, assume 1 coin has value of half total value. The first player can always select so second player cannot get that coin. Since the second player must always leave an even number, when he is given a choice of three and that high value coin is the middle one, it must be exposed for the first player. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 12, 2011 Report Share Posted August 12, 2011 Initial thoughts... The strategy should involve looking at the last two coins on either end. A player should always choose from the end that leaves the other player the lowest combination of deltas between the coins on the two ends (where delta is positive if the first coin in is greater than the one on the end, and negative if the first coin in is less than the one on the end). I think this strategy will optimize the choice. Player A has the advantage of going first which allows A to always be equal to or better than B for a given set of picks. Not sure how to express this mathematically at this point. Quote Link to comment Share on other sites More sharing options...
0 plasmid Posted August 13, 2011 Report Share Posted August 13, 2011 Number the coins from left to right, #1 through #100. On the first move, player one can take either an odd numbered coin (#1) or an even numbered coin (#100), and player two must then take whichever sort of coin (odd or even) that player one did not. On the second move, player one will again have a choice of taking either an odd or even coin, and player two must take whichever kind player one didn't. Therefore, player one can be guaranteed the opportunity to take either all of the odd coins or all of the even coins, and can choose whichever is greater. Quote Link to comment Share on other sites More sharing options...
0 CaptainEd Posted August 13, 2011 Report Share Posted August 13, 2011 Superprismatic, magnificent problem! Plasmid, magnificent answer! Besides the simplicity of the problem, I enjoy the tasty counterintuitivity--look at the 99 coin game, the person who "gets" to go first, and will thus draw more coins, can sometimes be forced to lose (ex. coins = 1 10 1)! Yet the first player in the 100 coin game can force at least a draw, as Plasmid showed so dramatically. Since Sp asked for the possibility of player 1 avoiding loss, Plasmid's answer suffices. It does not necessarily find the highest scoring strategy. (Hey, I'm impressed that a linear pass through the data gives a successful strategy at all!) If the coins (short game) were 7 5 20 8 6 13 19 15, Plasmid's strategy leads to player 1 getting a total of 52, but by starting by taking the 15, P1 can force a total of 54. Thank you folks for a great education! Quote Link to comment Share on other sites More sharing options...
0 OmegaScales Posted August 14, 2011 Report Share Posted August 14, 2011 I believe it would depend on the values, amount of each denomination, and placement of the coins. Correct me if I'm wrong, but it's impossible to know for certain without that information. Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 14, 2011 Author Report Share Posted August 14, 2011 I believe it would depend on the values, amount of each denomination, and placement of the coins. Correct me if I'm wrong, but it's impossible to know for certain without that information. It can be done without the information to which you refer. Remember, the problem is not to optimize return -- it only asks if either player can guarantee getting at least half the value of the coins. Quote Link to comment Share on other sites More sharing options...
0 OmegaScales Posted August 15, 2011 Report Share Posted August 15, 2011 One player can always gaurantee victory as long as there is no 50-coin combo worth the same value as the rest of the coins. Example: All but one coin is worth 2 "points", and the final one is worth 1 "point". There is a fifty-fifty chance of "John Doe" getting at least half the value (assuming each player takes the highest value coin available), depending solely on whether or not he goes first. If "Jane Doe" goes first he will definitely get less than half the value. If "John" goes first, he will definitely get more than half. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 15, 2011 Report Share Posted August 15, 2011 (edited) not sure that strat always works omega. consider... 2 4 8 2 -1 4 based on your method you should want 4,2,4. however: player 1 takes 4. if player 2 now takes the -1, would you take the 2 next to 8? player 2 takes the left 2 player 1 takes the -1! player 2 takes the 4. player 1 takes the 8. player 2 takes the 2. player 1 = 11. player 2 = 10. it seems something more is needed than just sum all odd, sum all even. Edited August 15, 2011 by phillip1882 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 15, 2011 Report Share Posted August 15, 2011 okay i think i got it. on each turn calculate which is the largest, removing both left, both right, or both ends. if both left or both right, remove the oppsite coin. if both ends, use larger of total all odd, total all even. exe: 7 5 20 8 6 13 19 15 7+5+20+8+6+13 = 59 20+8+6+13+19+15 = 81 5+20+8+6+13+19 = 71 player 1 removes 15. player 2 removes 19. 7 5 20 8 6 13 7+5+20+8 = 40 20+8+6+13 = 47 5+20+8+6 = 39 player 1 removes 13. player 2 removes 7. 5 20 8 6 5+20 = 25 20+8 = 28* 8+6 = 14 *both sides results in largest, use odd even. 5+8 = 13 20+6 = 26. remove 6. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 15, 2011 Report Share Posted August 15, 2011 hmm.. slight correction needed. if all odd or all even is greater than whats left after removing both left or removing both right, then you need to use that. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 16, 2011 Report Share Posted August 16, 2011 What if each player is to take 2 coins on his/her turn. they can take two from the same side or the two outer ones then what is the optimal strategy? Quote Link to comment Share on other sites More sharing options...
Question
superprismatic
Here is a two-player game in which the
players alternate turns:
100 coins of varying denominations are
placed in a single row on a table. A
player, during his turn, may take only
one coin from either end of the row.
Can either the first or second player
guarantee that they can accumulate at
least half of the value of all the
coins? If not, why not? If so, how?
Link to comment
Share on other sites
15 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.