Greedy coins game update

I plan to write a longer post soon, but for the moment I just wanted to provide a quick update about the greedy coins game (previous posts here and here). It turns out that the game is a lot more interesting—and has generated a lot more discussion—than I thought when I first posted it!

  • In my previous post I conjectured that the only tied games are the ones that can be built up by surrounding a tied game with a coin (cGc) or concatenating two tied games (G_1 G_2). That conjecture was quickly shot down, with commenters tinyboss and Thibault Vroonhove independently pointing out counterexamples: 1243 or 1342 are both tied, even though they can’t be built up in the conjectured way. As you can check, with best play in these games, one player will get 1 + 4 and the other will get 2 + 3.

  • Thibault noted that these particular tied games can be made by starting with a symmetric game (like 1331) and then adding the same number to all the coins in one half (e.g. adding 1 to each coin in the second half of 1331 yields 1342). However, although I think this always yields a tied game for games of length 4, it turns out that this does not always result in a tied game in general: for example, 123432 isn’t tied, since the coins add up to an odd total.

  • Thibault then came up with a counterexample to my other conjecture, namely, that G_1 G_2 is tied if G_1 and G_2 both are: 51151221 is not tied, even though it is the concatenation of two tied games. In fact, even 21121221 is not tied: Alice can guarantee that she will get at least three of the 2s.

  • Given all this it’s kind of amazing that the big game I constructed as a quick test of my conjectures, namely 01233244156650, is indeed tied. Eric Burgess reported that in fact every cyclic permutation of this game is tied!

  • Eric also introduced the function S, where S(c_i \dots c_j) denotes the winning margin, with best play, of whoever’s turn it is. That is, starting from position c_i \dots c_j, with best play, what is the difference between the current player’s score and the other player’s? (Note that in the case of Bob the “winning margin” can be negative, if Bob is going to lose even with best play.) If the current player takes coin c_i, then S(c_{i+1} \dots c_j) denotes the winning margin of the other player from that point on, which is the same as the losing margin of the current player. But they also got c_i; so overall their winning margin will be c_i - S(c_{i+1} \dots  c_j). Of course, best play means that the current player will choose whichever coin gives them the higher winning margin. This motivates the following inductive definition of S, where we use x \vee y to denote the maximum of x and y:

    • S() = 0

    • S(c) = c

    • S(c_i \dots c_j) = (c_i - S(c_{i+1} \dots c_j)) \vee (c_j - S(c_i  \dots c_{j-1}))

  • Thibault conjectured that the following strategy for Alice is optimal (I’ve rephrased it in a way that I’m pretty sure is equivalent, and which I think makes it more clear):

    • If the two end coins have unequal values, and the larger of the two is also larger than its neighbor, take it.

    • Otherwise, look at the alternating totals (i.e. the total of the “red” coins and the total of the “blue” coins). Take the end coin corresponding to whichever group has the higher total.

    • If neither of these rules apply then it doesn’t matter which coin Alice takes.

    If this strategy is indeed optimal, that would be really cool, since it is pretty easy to apply in practice. But I am not ready to say whether I believe this conjecture or not. In any case it should be possible to test this strategy with a computer program to play lots of random games, which I hope to do soon (and to write another post about it).

Posted in games, proof | Tagged , , , , , , | 10 Comments

Ties in the greedy coins game

In my previous post I described the “greedy coins game” and conjectured that the first player always has a strategy to win or at least tie. I had been unable to prove it, but suspected there must be some nice proof. Well, commenter Thibault Vroonhove rose to the challenge and came up with a beautiful, simple proof!

Color the coins alternately red and blue, like this:

Note that if she wants, Alice can play so as to take all the red coins and force Bob to take all the blue coins, or vice versa. For example, if she wants all the red coins, she starts by taking the red coin on the end, leaving Bob with no choice but to take a blue coin. Bob’s choice then exposes another red coin for Alice to take, leaving Bob with only blue coins to choose from, and so on. Symmetrically, Alice could always take the one available blue coin on her turn, leaving Bob with no choice but to take all the red coins.

So, if the sums of the red and blue coins are different, Alice can guarantee a win simply by choosing the set of coins with the higher total. If the red and blue coins have equal sums, Alice can at least guarantee a tie by arbitrarily choosing one set or the other.

Let’s call this strategy (taking either all the coins in even positions or all the coins in odd positions, whichever has the higher total) the “red/blue strategy”. This strategy constitutes a really elegant proof that Alice can never lose. But it’s not at all the end of the story—in particular, the red/blue strategy is not necessarily Alice’s best strategy! For example, consider this setup:

Notice that the “red” and “blue” coins have equal sums: 3 + 1 = 2 + 2. So if Alice just plays according to the red/blue strategy the result will be a tie. But Alice can do better: she should first take the 3, leaving Bob no choice but to take one of the 2s. But now there is a 1 and a 2 left, and Alice should obviously take the 2 (whereas the red/blue strategy would tell her to take the 1). So with best play Alice wins by a score of 5 to Bob’s 3.

This raises the natural question: when is a tie Alice’s best result? In other words, what sort of setups force a tie if both players play their best? Let’s call such setups “tied”.

As a first example, it is not hard to prove that symmetric games are tied. By a symmetric game I mean a game which stays the same when the order of the coins is reversed, i.e. where c_i = c_{2n-i + 1}. For example,

Theorem. Symmetric games are tied.

Proof. Bob can force a tie by always playing on the opposite side from Alice: that is, if Alice takes c_i then Bob takes c_{2n-i+1}, which has the same value by assumption. Since we already know that Alice will at least get a tie with best play, this must be the best result for both players (in particular, we know Bob cannot do any better with a different strategy).

However, this theorem does not completely characterize tied games. For example, the game

is also tied, even though it is not symmetric: each player will get 3 (if Alice starts by taking the 2, Bob takes the other 2, and then they split the 1s; if Alice starts by taking the 1, then it doesn’t matter what Bob takes next; on her next turn Alice will take a 2).

Can we completely characterize which games are tied? I will close by stating an observation, a theorem, and a few conjectures.

Observation. The empty game (consisting of zero coins) is tied, since after zero moves both players end with a value of zero. (This one is not really worth calling a theorem!)

Theorem. If G is tied, then so is c G c, the game obtained from G by adding two copies of the coin c, one on each end.

Proof. Bob can force a tie: after Alice takes one copy of c, Bob takes the other one, and now the game is reduced to G, which is tied by assumption.

Note that all symmetric games can be built up in this way, by starting with the empty game and successively adding “layers” that look like cGc. So this observation and theorem together constitute an alternate, inductive proof that all symmetric games are tied.

If G_1 and G_2 are games (that is, sequences of an even number of coins), let G_1 G_2 denote the game obtained by concatenating the sequences of coins. For example, if G_1 = 3,4,4,3 and G_2 = 5,5 then G_1 G_2 = 3,4,4,3,5,5.

Conjecture. If G_1 and G_2 are both tied, then so is G_1 G_2.

For example, we know 3,4,4,3 and 5,5 are both tied since they are symmetric. This conjecture then claims that the game 3,4,4,3,5,5 is tied as well (which happens to be true in this case, as you can check).

As a more interesting example, the foregoing theorem and conjecture (if true) could together be used to show that 01233244156650 is tied (I’m tired of writing the commas in between single-digit coin values), because this game can be broken down as 0(1((2(33)2)(44))1)(5(66)5)0. And guess what, I have verified computationally that this game is indeed tied! (I’ll discuss how to do this in a future post.)

Conjecture. This completely characterizes tied games: a game is tied if and only if it is inductively built up, starting from the empty game, by applications of the foregoing theorem and conjecture.

I believe this conjecture less than I believe the first one. There might be other strange ways to build tied games.

Posted in games | Tagged , , , , | 22 Comments

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!

Posted in games | Tagged , , , , | 14 Comments

Post without words #15

Image | Posted on by | Tagged , , , , | 8 Comments

Post without words #14

Posted in pattern, pictures, posts without words | Tagged , , , , | 14 Comments

Fibonacci’s Problem of the Birds

I have been enjoying reading Keith Devlin’s new book, Finding Fibonacci. I’ll write more about the book later. For now, I just wanted to share a nice problem I learned about which Leonardo Pisano, aka Fibonacci, included in his book Liber abbaci. First published in 1202, this is the book that introduced the Hindu-Arabic number system to the Western world. Apparently this problem is well-known among mathematicians, but I had never heard it. Here it is, as translated from Latin by Laurence Sigler:

A certain man buys 30 birds which are partridges, pidgeons, and sparrows, for 30 denari. A partridge he buys for 3 denari, a pigeon for 2 denari, and 2 sparrows for 1 denaro, namely 1 sparrow for 1/2 denaro. It is sought how many birds he buys of each kind.

Can you solve it?

Posted in algebra, arithmetic, challenges, people | Tagged , , | 6 Comments

Post without words #13

Image | Posted on by | Tagged , , | 15 Comments