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: . 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 . 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 then Bob takes , 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 is tied, then so is , the game obtained from by adding two copies of the coin , one on each end.
Proof. Bob can force a tie: after Alice takes one copy of , Bob takes the other one, and now the game is reduced to , 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 . So this observation and theorem together constitute an alternate, inductive proof that all symmetric games are tied.
If and are games (that is, sequences of an even number of coins), let denote the game obtained by concatenating the sequences of coins. For example, if and then .
Conjecture. If and are both tied, then so is .
For example, we know and are both tied since they are symmetric. This conjecture then claims that the game 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 is tied (I’m tired of writing the commas in between single-digit coin values), because this game can be broken down as . 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.