A row of coins is already a sum

A row of coins, some showing heads and some tails. A move turns over one or two coins, subject to a single condition: the rightmost coin turned must go from heads to tails. A player who cannot move — which happens exactly when every coin shows tails — loses.

The condition is what makes the game end, and it does so for a reason worth seeing straight away. Read the row as a binary number with a one for each head. Turning the rightmost head to tails always makes that number smaller, whatever happens to the coins on its left, because the bit it clears outranks every bit that changes. So play strictly descends through the non-negative integers and cannot go on for ever.

The sum is inside the position #

Everywhere else in this subject a disjunctive sum is a collection of separate positions — several Hackenbush sprigs, several regions of a board — and a move is a move in exactly one of them. Adding them up is a step the analyst takes after decomposing something.

Here the decomposition is already done, and by the rules rather than by the analyst.

Consider the row with a single head, at place $n$, everything else tails. Call that game $\langle n \rangle$. The claim is that a row with heads at $n_1, n_2, \dots$ is worth exactly

$$\langle n_1 \rangle + \langle n_2 \rangle + \cdots,$$

the disjunctive sum of the one-coin games — so its Grundy value is the exclusive or of theirs, by the Sprague–Grundy theorem.

Why that should be true is not obvious, because a move can turn two coins at once, which looks like a move in two components. The resolution is that turning a coin is its own inverse: a move that turns coins at $a$ and $n$ is a move in $\langle n \rangle$ and in $\langle a \rangle$ simultaneously, and turning a tail at $a$ into a head is the same operation as turning a head there into a tail. Adding a component and removing one are the same act, so a two-coin move stays inside the sum.

Put three of those side by side and the picture at the top of the page comes out, with heaps of 3, 5 and 8 and a total of ∗14. Everything a reader knows about Nim applies to a row of coins from that moment, and no step of the argument mentioned coins.

The move that turns two coins at once #

The step that carries the whole argument deserves more than the sentence it got, because it is the one place where a coin-turning game does something no other sum on this site does.

In an ordinary disjunctive sum a move touches exactly one component. Turning coins at places $a$ and $n$ with $n$ rightmost touches two — so on the face of it this is not a disjunctive sum at all, and the theorem should not apply.

It applies because of what “touching” means here. The head at $n$ becomes a tail: the component $\langle n \rangle$ is removed from the sum. The coin at $a$ flips: if it was a tail it becomes a head, adding $\langle a \rangle$; if it was a head it becomes a tail, removing $\langle a \rangle$. Either way the effect on the sum is to add $\langle a \rangle$ — because in this setting adding a component twice is the same as not adding it, exactly as $\ast k + \ast k = 0$.

So a two-coin move is: remove one component, and add the exclusive or of another. That is a move in the sum, and it is legal in $\langle n \rangle$ considered alone, since a lone head at $n$ can be turned along with any tail at $a$. The set of moves available in the sum and the set available in the component are the same set. Nothing has escaped the theorem.

Why twice is the same as not at all is the right arithmetic here is worth saying in one more sentence, because it is the only place the two halves of the essay touch. The nim-sum adds binary columns without carrying, so every value is its own inverse and $\ast k + \ast k = 0$ for every $k$. Turning a coin twice returns it to where it started. Those are the same statement, one about arithmetic and one about a game, and the decomposition is what identifies them.

A row nobody wants to move in #

The consequence is that a coin-turning game has losing positions with no visible symmetry whatever.

The equivalent Nim position can be played, which is the sharpest test the claim admits: if a row of coins really is a Nim position with heaps 3, 5 and 6, then losing the heaps is losing the row.

That is the difference between a game with a value theory and a game with a trick. Somebody who knows only that “the row is lost” has to remember a list of rows; somebody who knows the value computes it from three numbers and a pair of exclusive-ors. The same distinction runs through Nim, and it is the reason a solved game is worth more than a table of answers.

Three rules, three patterns #

The claim so far is structural and holds for the whole family. What each particular game produces is a separate question, and this is where the family stops being a curiosity.

Change the rule from “turn one or two coins” to “turn one, two or three”. Change it instead to “turn any consecutive run”. Both are still coin-turning games, both still decompose the same way, and the tables of one-coin values that come out are not remotely alike.

Turning Turtles — one or two coins — gives $g(n) = n$. The row is Nim with a heap for each head, of size equal to its place. That is as clean a correspondence as this subject offers, and it is why the game is the standard first example.

Mock Turtles — one, two or three coins — gives the odious numbers: those with an odd number of ones in binary. $1, 2, 4, 7, 8, 11, 13, 14, 16, \dots$ Nothing in “turn one, two or three coins” mentions binary digits.

Ruler — any consecutive run — gives the largest power of two dividing the place: $1, 2, 1, 4, 1, 2, 1, 8, \dots$ That is the pattern of tick heights on an imperial ruler, which is where the name comes from, and again nothing in the rule mentions powers of two.

How the table is built, and why it is cheap #

The construction of those tables is the second thing worth noticing, and it is a consequence of the decomposition rather than an application of it.

To find $g(n)$ — the value of a lone head at place $n$ — take the mex over the moves available. A move turns some set $S$ of coins with $n$ rightmost, so it clears the head at $n$ and flips every other coin in $S$ from tails to heads. The position left behind has heads exactly at $S \setminus \{n\}$, and by the decomposition its value is the exclusive or of their one-coin values — all of which are to the left of $n$ and so already known.

$$g(n) = \operatorname{mex}\Bigl\{\; \bigoplus_{i \in S,\; i < n} g(i) \;\;\Bigm|\;\; S \text{ a legal move with } n \text{ rightmost} \Bigr\}.$$

So the whole table is built left to right, each entry from the entries before it, with no search over rows at all. Sixteen places for three games is a few hundred exclusive-ors.

The rule doing all the work there is the mex: a position’s Grundy value is the smallest non-negative integer that is not the value of any option, so a value is determined entirely by which values the options reach and never by how many options there are or how they are spelled. That is why a table of one-coin values settles a game whose rows number in the thousands.

That is a genuine payoff and not merely a tidy one. Solving a row of $k$ coins directly means examining up to $2^k$ positions; building the table takes work proportional to $k$ times the number of moves at each place. For twelve coins the difference is four thousand positions against a hundred and fifty exclusive-ors, and the gap widens without limit — which is the ordinary shape of the difference between having a closed form and not having one, arrived at here by a structural theorem rather than by a clever algorithm.

That row is a win for the mover, and in Mock Turtles a row with three heads always is. The reason is a single line of parity and it is worth extracting, because it is the only place in the family where the pattern in a value table decides something about rows rather than about places. Every one-coin value is odious, which is to say it has an odd number of ones in binary; exclusive or adds those counts column by column without carrying, so the parity of the count adds too. Three odd counts sum to an odd count, so the total is odious, so it is not nought. No Mock Turtles row with an odd number of heads is ever a loss. The losing rows all have an even number, and the smallest of them are four heads wide.

Turning Turtles has no such restriction, because its values are the counting numbers and 3 ⊕ 5 ⊕ 6 is nought, as the losing row above shows. Two rules a phrase apart, and one of them has a parity law about its rows that the other has not.

Where the counting numbers come from #

The three patterns are presented above as things the tables happen to produce, and one of them can be derived in two lines from the recursion — which is worth doing, because it shows how little the answer depends on anything.

Turning Turtles allows a move to turn one coin or two. A move with the head at place $n$ as its rightmost coin is therefore either $\{n\}$ alone, leaving the empty row, or $\{a, n\}$ for some place $a$ to the left, leaving a lone head at $a$. So the options of a lone head at $n$ are worth $0$ and $g(a)$ for every $a < n$, and

$$g(n) = \operatorname{mex}\{\,0\,\} \cup \{\,g(a) : a < n\,\}.$$

Take $g(a) = a$ for every place before $n$, as an induction hypothesis. The set is then $\{0, 1, 2, \ldots, n-1\}$, whose mex is $n$. The base case is $g(1) = \operatorname{mex}\{0\} = 1$.

That is the whole proof, and what makes it work is that “turn one or two” gives a lone head an option leading to every smaller value and nothing else. A rule that reached fewer values would leave a gap for the mex to fall into; a rule that reached more would have to reach them from somewhere, and there is nowhere left of $n$ but the places already counted.

Every coin-turning game is solved #

The derivation used the rule. The decomposition did not, and that is the fact worth carrying out of this essay.

Read the argument again and notice what it never mentions: how many coins a move may turn, whether they must be adjacent, whether the set has any shape at all. All it uses is that a move’s rightmost coin goes from heads to tails, and that turning a coin is its own inverse. So the theorem holds for any choice of allowed turning patterns whatever — the three games above, the dozen relatives in the literature, and every rule nobody has bothered to name.

Which means the whole family is solved by construction. Pick any rule of this shape and the one-coin table is built left to right by the recursion above, each entry a mex over exclusive-ors of entries already computed; the row is the sum of its heads; the value follows. There is no game in this family that anybody has to search.

The way to believe that is to run it on a rule chosen for awkwardness rather than for elegance. Mogul is Mock Turtles with the three coins confined to a window of seven places — a restriction that sounds arbitrary and is the one that makes an error-correcting code fall out of the game. Its table opens exactly as Mock Turtles’ does, 1, 2, 4, 7, 8, 11, 13, and then does something Mock Turtles never does: the eighth place is worth 1 again, because the window has cut precisely the moves that would have taken the value higher. The table is those seven values on repeat, for ever.

Nothing in the construction noticed. The same recursion built that table from the same exclusive-ors, and the same decomposition read the row off it; the bounded table is a fact about Mogul rather than a difficulty for the method.

Set that beside the octal games and the contrast is startling. An octal game is also specified by a short code, is also impartial, and is also a heap game with a one-line rule — and the Grundy sequence of $\cdot 007$ is an open problem that has consumed decades of computation without settling. Two families, comparable descriptions, and one of them is entirely solved while the other contains questions nobody can answer.

The difference is exactly the one this essay is about. An octal heap is not a sum of anything. Removing tokens from a heap of $n$ produces a heap of some smaller size, and the value of a heap has no expression in terms of smaller heaps except through the mex — so the sequence has to be computed term by term and can do whatever it likes. A row of coins is a sum, so its table is built from an operation that is known in advance to be the exclusive or, and the only thing left to compute is one value per place.

That reverses the usual reading of the family. Coin-turning games look like an artificial construction chosen to make a decomposition available — and they are — but the artificiality is the whole content. Being a sum is not a convenience that makes a game easier; it is the difference between a family with no open problems in it and a family with famous ones.

Checked on every row, not on the drawn one #

A figure shows one row. The claim is about all of them, and a decomposition that held on the rows an author happened to pick and failed elsewhere would look exactly the same in a picture.

So the site’s gate takes each of the three games and, for every one of the 4,096 rows of twelve coins, computes the value two ways. Once by the decomposition — exclusive or of the one-coin values of the heads. Once by brute force — enumerating the row’s moves as a single impartial game, memoising on the whole row, taking a mex, and knowing nothing whatever about one-coin values.

Twelve thousand two hundred and eighty-eight comparisons, and no disagreements.

The second computation is deliberately ignorant. It would be easy, and useless, to write a “check” that recomputed the exclusive or by a slightly different route; what makes this evidence is that the direct solver treats a row as an ordinary position and would find a discrepancy if the decomposition were wrong in any case at that size.

The gate also checks the three patterns separately, and checks that they are different from each other — because “the computed values match the claimed pattern” would pass trivially if the claimed pattern were being read out of the computed values.

What the solver computed, and how #

coinValues(game, upTo) builds the table by the recursion above. It requires every move it is given to have $n$ as its rightmost coin and throws otherwise, which is the condition the whole family depends on and the easiest one to get wrong when adding a new rule.

rowValueDirect(game, row) solves a row as a single game. Its state is a bitmask of the heads; its moves are, for each head $n$, every legal turning set with $n$ rightmost, applied by exclusive-or on the mask; its value is a mex over the results, memoised.

checkDecomposition(game, length) runs both over every mask from $0$ to $2^{\text{length}} - 1$ and returns the disagreements. The figures call it indirectly: coin-row computes both values for the row it is about to draw and throws if they differ, so a broken decomposition would stop the build at the first figure rather than at the gate.

The mex is the same three-line function the rest of the site uses. Nothing about coin-turning games is special-cased anywhere except in the move tables.

Where the model stops #

Sixteen places, twelve coins. The tables are drawn to sixteen and the exhaustive check runs at twelve, where $2^{12}$ rows is a second of work. At twenty coins the exhaustive check would take a day and the tables would be no harder, which is the whole asymmetry the essay is about — but it means the verification is at one size and the claim is at all sizes.

The patterns are checked, not proved. That Mock Turtles gives exactly the odious numbers is a theorem with a proof; what happens here is that sixteen values are compared against sixteen predictions. Sixteen agreements are evidence and are not a proof, and the essay does not pretend otherwise.

The termination argument is about the row, not about the moves. Reading the coins as a binary number is what proves the game ends, and it is worth noticing that no individual move is required to make the position smaller in any other sense — a move can turn two tails into heads and leave more coins showing than before. This is the same distinction Poker Nim turns on: what the recursion needs is a well-founded order, not a quantity that visibly shrinks, and a game can satisfy the first while flouting the second.

Two dimensions are not covered. The family extends to coins on a grid, where a move turns a rectangle of them and the values are given by a product of the one-dimensional tables — Tartan games, and a genuinely surprising construction. Nothing here touches it.

Who found it, and when #

Coin-turning games are laid out in Winning Ways (1982), where Berlekamp, Conway and Guy give the family its name, prove the decomposition, and work out Mock Turtles, Ruler, Mogul and a dozen relatives. The Mogul case is the striking one: its values are Mock Turtles’ restricted to a window of seven, and the analysis runs straight into the Hamming code — an error-correcting code turning up in a game about flipping coins.

The decomposition itself is the Sprague–Grundy theorem doing what it does, and the theorem is from 1935 and 1939. What the coin-turning family adds is a setting in which the sum is not something the analyst imposes on a position but something the rules hand over, already assembled.

The same family in two dimensions #

A row is already a sum. So is a grid, and the values it holds are not the ones a reader would guess.

Put the coins on a rectangle and let a move turn every coin at a square of $X \times Y$, where $X$ is a legal turn of one game and $Y$ of another, with the bottom-right corner going from heads to tails. A grid is then the sum of its heads for exactly the reason a row is, so again one table of single-coin values settles everything — and the table is not the exclusive or of the two edge tables. It is their nimber product, which is a multiplication defined by a mex over products and has no business appearing in a game about flipping coins. The tartan theorem checks it cell by cell over several pairs of factors and kills the three combining rules a reader would try first, Ruler against Ruler among them.

Where the ladder goes next #

This is the second rung on the Sprague–Grundy ladder. The first states the theorem and shows every impartial position collapsing to a single heap; this one finds a family where the collapse happens inside one picture.

The rung after asks what the tables do at length. Grundy sequences are eventually periodic for finite subtraction sets, and the coin-turning tables have their own periodicities — Ruler’s is visible at a glance and Mogul’s has period seven — but Mock Turtles’ odious numbers are not periodic at all, which puts three games from one family on three different sides of the question the octal games leave open.