[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?

[Guest]

Can values be duplicated (e.g 99 coins worth 1, and 1 coin worth 2)?

[superprismatic]

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.

[Guest]

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

[superprismatic]

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.

[Guest]

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.

[Guest]

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.

[plasmid]

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.

[CaptainEd]

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!

[OmegaScales]

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.

[superprismatic]

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.

[OmegaScales]

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.

[Guest]

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

[Guest]

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.

[Guest]

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.

[Guest]

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?