## The greedy coins game

Here’s an interesting game I’ve been thinking about.1

There is a row of $2n$ 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 $2n$ 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!)

1. I got this problem from the Consortium for Computing Sciences in Colleges Mid-South 2012 programming contest (problem C).

2. That’s why I got this problem from a programming contest!

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in games and tagged , , , , . Bookmark the permalink.

### 19 Responses to The greedy coins game

1. Given the stated rules, a trivial refutation exists when all coins have the same value. Then the outcome is a tie and it doesn’t matter who plays first or what strategy s/he uses.

For non-trivial cases, I would need to do more than 5 seconds of thinking. 🙂

For the example you give, the total value of the coins if 43, so if one player can capture 22 or more points, s/he wins. If Alice takes the 8, she has to win. Bob can take the 9, then Alice takes the 1 and no matter what Bob does, Alice gets the 17 and wins.

If Bob takes the 1 on his first move, Alice takes the 9 and again, Bob is going to have to let her take the 17 for the win (by more). Thus, Bob’s “optimal” move is to take the 9, then after Alice takes the 1, he will take the 3 (or 5, it doesn’t matter) and after Alice takes the 17, Bob gets the remaining 3 or 5 and winds up with a total of 17, his best possible total if Alice plays correctly.

Interestingly, Alice still wins if she takes the 1 to start. If Bob then takes the 3, Alice takes the 17, giving her 18 already and a guaranteed win no matter what she takes on her last move. If Bob takes the 8 on his first move, then Alice takes the 9, and once again Bob is going to lose whichever coin he takes next. So Alice can play her SECOND-BEST initial move and still force a win.

I suspect things might get more interesting with the player who goes second getting two moves in a row to start. I can also imagine an odd number of coins but with coins of large values being second and second to last creating some interesting strategic tensions. Will have to play more.

• Brent says:

Your idea of giving the second player two moves in a row is interesting indeed. Notice that in the given example (1 3 17 5 9 8) the second player will win if given two moves in a row, by taking either 9 8 or 1 9. But it’s also easy to create initial situations where the first player still wins even if the second player gets two moves (e.g. 100 1 1 1). More generally, I wonder if the “fairest” move sequence would be something like the Prouhet-Thue-Morse sequence — though I’m not sure exactly how to characterize what “fairest” means here.

2. Another easy counter-example with four coins: let the two outside coins have the same value and let the two inside coins have equal but greater value than the outside coins. Again, a tie must result if both play optimally. For six coins, let the arrangement be 1 2 3 3 2 1 and again, Bob can force a tie by taking the exposed 2 after Alice plays, then taking the exposed 3 after she takes the other 3, and finally taking the remaining 1: each get 6 and there’s no way for Alice to improve on that via strategy. So symmetrical arrangements present a problem for her, I suspect.

• Brent says:

Yes, good point! I knew about such cases but I somehow just wasn’t thinking about them when I wrote down my conjecture. I’ve revised the conjecture to say that the first player has a non-losing, rather than a winning, strategy.

3. Alice can’t possibly force a win in the game 1 3 1.

• True, but the game calls for 2n coins, an even number, so that arrangement isn’t in this game’s rules.

• Ah, missed that, thanks!

4. Thibault Vroonhove says:

Well, it is always possible for Alice to get at least a tie, and here is a simple strategy to do so :
– assign colours to the coins so that the 1st, 3rd, …, (2n-1)th ones are red and the 2nd, 4th, …, (2n)th ones are blue
– then, if (with no loss of generality) the total value of the red coins is greater (or equal) than the total value of the blue coins, pick the 1st coin (that is red) so Bob will have to pick a blue one – freeing a red one, and then just go on picking that red one : you’ll get all the red coins and consequently at least as much as Bob

• Brent says:

Oh, very nice! I see it now. Spot on.

• Juan Valera says:

Cool… it’s the prove @Brent was asking for.

5. Bill Kinnersley says:

It’s worth noting that a cyclic version of this game, phrased in terms of eating pizza, has been reasonably well studied: see https://arxiv.org/abs/0812.2870 . I would expect that the games are very closely connected.

6. Pingback: Greedy Math Games – The Square Root