Here’s an interesting game I’ve been thinking about.1
There is a row of coins on the table; each coin can have any positive integer value. Two players alternate turns. On a player’s turn she must take one of the two coins on either end of the row of remaining coins, so with each turn the row gets shorter by one. After all the coins have been taken, the player with the higher total value is the winner.
Let’s look at an example. Suppose the coins start out like this:
The first player (let’s call her Alice) can choose either the 3 or the 2. Let’s say she takes the 3. (3 is bigger than 2, right?) Now the table looks like this:
The second player (let’s call him Bob) is now allowed to take either the 5 or the 2. His best move is clearly to take the 5, since it’s even bigger than the other two remaining coins combined. After that the table looks like this:
Finally Alice takes the 2, and Bob takes the 1. Final score: Alice 5, Bob 6. Bob wins!
…except it turns out, as you may have already noticed, that Alice’s first move wasn’t her best choice! It’s very easy to come up with examples, like this one, which show that the obvious “greedy” strategy—namely, always take the biggest coin available to you—is not the best strategy for this game.
So, what Alice should have done is start by taking the 2, leaving this:
Whoever gets the 5 is going to win, because even the 5 combined with the smallest coin, 1, is still larger than the sum of the others. By taking the 2, Alice leaves the 5 “protected” so Bob can’t take it on his next turn—he has to take one of the coins next to it, which will allow Alice to take it. Bob might as well take the 3, and then Alice takes the 5, leaving the 1 for Bob. Final score: Alice 7, Bob 4. So in this scenario, Alice actually wins if she plays her best. Can you come up with other sorts of example scenarios? …such as a game where the first player will end up with the same result no matter which first move they play (even though the two coins are different)? A game where the two players tie if they both play their best (even though all the coins are different)? A game where the first player loses when both players play their best? What if we allow negative or fractional coins?
This is a fun game to play, and it’s not at all obvious, in general, what the best strategy is. Here’s one for you to analyze. What is Alice’s best move if the game starts in the position shown below? And what is Bob’s best follow-up move? Leave your analysis in the comments!
To play this game realistically with a friend, one could use a sequence of real coins, e.g. 1 cent, 5 cent, 10 cent, and 25 cent coins (if using US coins). Does the analysis of the strategy become any easier if we restrict ourselves to only having these particular coin values (or any other particular set of coin values)?
It is actually feasible to write a computer program that will calculate the optimal play for any given sequence of coins2; I may write about that a bit in a future post. For now, I want to share a conjecture about the game:
Conjecture: the first player always has a
winning non-losing strategy.
That is, if the first player plays optimally, they will always
win either win or tie. I strongly suspect this is true, but I have so far been unable to prove it. On the other hand, I don’t think my inability to prove it necessarily means it’s hard to prove; I think it just needs the right insight. Can you either prove this, or find a counterexample? (Note that it may be possible to prove this non-constructively, that is, it may be possible to prove that the first player will always win or tie without saying what their actual strategy is!)
I got this problem from the Consortium for Computing Sciences in Colleges Mid-South 2012 programming contest (problem C).↩
That’s why I got this problem from a programming contest!↩