Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's play a game:

There are $n$ stacks of coins in a row. $i$-th stack consists of $d_i$ coins. Two players: $\text{Player1},\text{Player2}$ make moves alternately. Player in his turn can only take first stack or last stack or both of them. The game ends when there are no coins left. Each player wants to have as many coins as possible at the end. $\text{Player1}$ starts.

Is it even possible to create an optimal strategy for both players? I was wondering about algorithm (sounds like greedy algorithm) to count how many coins each player has at the end of the game when both plays optimal.

My first intuition was that $\text{Player1}$ is always one step ahead $\text{Player2}$ and has more coins at the end. But it is of course wrong.

Examples (coins in stacks from first to $n$-th):

$1, \ 100, \ 1$ - players have $2$ and $100$ coins respectively (unfortunately first player can only take first and last stack - second player will always take stack with $100$ coins)

$1, \ 1, \ 100, \ 1, \ 1, \ 5$ - players have $8$ and $101$ coins respectively (I think this is after optimal game - first take $5$ and $1$, then second take $1$ to prevent player1 from taking stack with $100$ coins. If player1 take less than $6$ coins in first turn he will always have less than $8$ coins).

I hope I specified enough the problem. Do you agree that it is interesting? :) Can anybody help?

share|improve this question
    
Since the game is finite, there must be a winning strategy for one of the players, or they both have a strategy to gain the same score. –  yo' Nov 26 '12 at 20:15
    
There is almost certainly a dynamic programming solution; it's almost equivalent to another problem I've seen with the exception that you can take both stacks. –  Merbs Nov 27 '12 at 22:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.