[Guest]

This is the game:

There are 100 slips of paper in a row, each piece of paper has an integer written on it (all the slips of paper are face up so everyone can see the numbers). During each player's turn he may choose to take the paper on the far left, or far right side of the row and add it to his score. The winner is the person who has the largest score at the end of the game, when there are no more slips of paper in the row.

a) Can you come up with a strategy that the first player can use and prove that the first player will never loose using that strategy? (He will win or tie)

b) Can you prove the strategy works (or come up with a different one) for n slips of paper?

The idea is to come up with something you can prove works, not something that seems to work.

The best strategy might not be the easiest to prove.

Edited February 7, 2011 by K4D

[Guest]

are we doing it for integers 1 to 100 or just any integers with repetition allowed?

[Guest]

Any integer, positive or negative, could be written on each slip of paper. Repetition is allowed.

[k-man]

There isn't a strategy that guarantees a win to the first player regardless of how the numbers are arranged. For example, if all cards alternate 0s and 1s like this 0, 1, 0, ... 0, 1, 0 then the first player will always lose by getting 0 points. The second player will collect all the 1s.

However, there likely is a strategy to maximize the score given the layout. I will think about that...

[superprismatic]

There isn't a strategy that guarantees a win to the first player regardless of how the numbers are arranged. For example, if all cards alternate 0s and 1s like this 0, 1, 0, ... 0, 1, 0 then the first player will always lose by getting 0 points. The second player will collect all the 1s.

However, there likely is a strategy to maximize the score given the layout. I will think about that...

I think your example ends in a 1-1 tie, not a win for the second player.

[Guest]

a layout like 0,1,0,1,0,1...0,1,0 would give player 2 the victory with an odd number of cards.

however, with an even number of cards, like 0,1,0,1,...1,1,0,1,0,1...0,1,0 gives a tie at worst for player 1.

with 6 cards, lets say the cards are:

-10,35,65,100,3,7

obviously both players want the 100. so palyer 1 starts off taking the 7.

now player 2 cannot take the 3, else player 1 wins. so player2 takes the -10.

so player 1 takes the 35. palyer 2 has no choice but to take the 65. player 1 takes the 100, and wins.

now lets arrange the cards differently.

3,100,35,-10,65,7

here the 100 isn't quite as valueable as it apears.

player 1 takes the 3. player 2 has no choice, takes the 100.

player 1 takes the 35. player 2 agian has little choice, takes the 7.

player 1 takes the 65 (103 points for player 1) and player 2 takes the -10, (97 points for player 2.)

now how to prove that player 1 always gets the win with an even number of cards?

[k-man]

I think your example ends in a 1-1 tie, not a win for the second player.

Yeah, I didn't think it through when I posted this, so I stand by my original answer for any ODD number of cards. For odd number of cards you can't force a win or a tie. But if the number of cards is even, then...

Number all the cards from left to right - (e.g 1,2,3,...n)

Add up all the odd numbered cards - 1,3,5 etc. and all the even cards - 2,4,6, etc.

If the sum of the odd cards is greater than the sum of even cards pick from the left end. If the sum of even cards is greater pick from the right. If the sums are the same, it doesn't matter which side to start from as unless the second player makes a mistake it will be a tie.

This strategy works because you are forcing your opponent into choosing from the set of cards that has a smaller sum.