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 () or concatenating two tied games (). That conjecture was quickly shot down, with commenters tinyboss and Thibault Vroonhove independently pointing out counterexamples: or 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 and the other will get .

Thibault noted that these particular tied games can be made by starting with a symmetric game (like ) and then adding the same number to all the coins in one half (e.g. adding to each coin in the second half of yields ). 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, 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 is tied if and both are: is not tied, even though it is the concatenation of two tied games. In fact, even is not tied: Alice can guarantee that she will get at least three of the s.

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

Eric also introduced the function , where denotes the winning margin, with best play, of whoever’s turn it is. That is, starting from position , 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 , then 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 ; so overall their winning margin will be . 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 , where we use to denote the maximum of and :

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).
