23 Nov 2011
There are an even number of coins arranged in a straight line. You and your friend may only take coins from either ends. You and your friend take turn to take one coin at a time until there are no coins left. The one with the larger sum of coins's value wins. If equal, you win. Could you think of a winning strategy if the first turn is yours?
Let's start with a simple case:
1, 2, 3, 4
In this case, I should take 4 first, and no matter what my friend takes, I will take 2 next.
I will end up with 6 and my friend will end up with 4. I win
2, 1, 3, 4
I will still take 4 first, my friend will definitely take 3 (otherwise, I will end up with a larger value). I will take 2 next this time.
At the end, I will end up with 6 and my friend will end up with 4.
Here I can see a pattern that I have power to control the game because, when I take an even-position coin, only odd-position coins are present at both ends.
This means I can either choose all even-positioned coins or all odd-positioned coins.
Therefore, an OK solution is to decide by comparing the sum of even-positioned coins's value and odd-positioned coins's value.
Well, that is easy.
Could you maximize the value that you are going to get?
Ok, the first thing to remember is that, when we solve a multiple-person game, we have to assume that every person knows the same winning strategy. It's just that they cannot execute it because of constraints.
Let's try an example that the above solution does not maximize the value:
1, 2, 1000, 3, 4, 900
With the above solution, I have to take 1, 1000, and 4. But actually I can take 900, 1, and 1000.
This is because when we take 900 at first, we get:
1, 2, 1000, 3, 4
We can see that 2, 1000, and 3 are “safe”. My friend can either take 1 or 4 and I still get 1000 anyway because I control the position's parity.
After I and my friend take one turn each, the game is back in its initial form. And I can re-choose my strategy again.
Since the game is reduced, we can devise a strategy to focus on only 1 turn at a time.
Let's say a, a, …, a[n-1], a[n] is the coins.
If I take a, then my friend can either take a or a[n]. If I take a[n], then my friend can either take a or a[n-1].
Therefore, the best decision is to maximize the difference between my friend and me.
choose_1 = a - max(a, a[n]) choose_n = a[n] - max(a, a[n-1]) if choose_1 > choose_n we take a[n] else we take a end
Anyway, this solution has a big flaw.
Even there is a safe zone, the sum of that safe zone might be less in value than the coin my friend takes. For example,
1, 2, 6, 4
Following the strategy, I have to take 2 first.
The problem is that 2 is in the safe zone, but its sum is less than 6. Therefore, we need to add some condition to handle this case.
Consider a little more complicated example:
1, 1, 4, 1, 6, 4
If we take 1, 4, and 6, we get 11. But if we try to maximize by getting 4 first, we'll end up with 4, 1, and 4, which is 9.
The previous solution is better in this case!
From this point, I have realized that the decision to take a coin at one moment depends on the setting of the coins.
I don't think there is an analysis to this problem.
Since the game can be reduced, a dynamic programming approach is possible.
We let V[i, j] = the maximum value we are going to get from the game with a[i], …, a[j]
The base cases: V[i, i+1] = max(a[i], a[i+1]) The complex cases: V[i, j] = max(a[i] + min(V[i+2, j], V[i+1, j-1]), a[j] + min(V[i, j-2], V[i+1, j-1]) )
min(V[i+2, j], V[i+1, j-1]) means that my friend tries to pick whatever coin to minimize my value.
And we only iterate the number where j - i + 1 is even.