The pairs are read from the bottom bits

Welter’s game is Nim with one clause added: coins on a strip slide to lower empty squares, and no two may share a square. No two heaps alike found its closed form. The Grundy value is the exclusive-or of Welter’s animating function $\langle a \mid b \rangle = (a \oplus b) - 1$ over every pair of coins, with the plain nim-sum of the squares added when the number of coins is odd. The pairing the formula hides read that formula as a matching. Some way of pairing the coins off, with the one left over contributing its own square when the count is odd, has animating values that exclusive-or to the value — on every position it measured, and on most of them only one matching does.

That essay left the obvious question as the thing to do next. If one matching usually works and the others do not, the matching of a position is a well-defined object, and something about the squares ought to pick it out. Nothing it computed did so except trying every matching and keeping the one that worked. It suggested where to look — coins agreeing in their high bits, or coins whose squares are close — and both of those turn out to be wrong. The rule reads the squares from the other end.

Five rules, and the one that is never wrong #

Five ways of choosing a matching are worth trying, because each is what a reader looking at a strip of coins might do first.

Neighbours in order pairs the two lowest coins, then the next two, and so on, which is what the strip suggests. Outermost first pairs the lowest coin with the highest and works inwards. Closest numbers repeatedly pairs the two coins whose squares differ least. High bits repeatedly pairs the two whose squares exclusive-or to the smallest number, which means they agree in as many leading bits as possible. And low bits repeatedly pairs the two whose squares agree in as many trailing bits as possible — whose binary expansions, read from the right, run together longest before they part.

Every rule reads the value on every two-coin position, because two coins admit only one matching. From three coins on they separate sharply. Low bits is right on all 364 three-coin positions, all 1,001 four-coin ones, 792 of 792 at five, 924 of 924 at six, 330 of 330 at seven and 165 of 165 at eight. The next best rule, outermost first, is right on 501 of the 1,001 four-coin positions and 71 of the 165 eight-coin ones; the rest do worse. Nothing about the strip’s own geometry picks the pairs. The squares’ positions on the strip matter only as numbers, and it is their last bits that decide.

It is also the reverse of where Nim looks. The winning move in Nim is found at the top: take the highest bit of the nim-sum, find a heap that has it, and reduce that heap. A reader who knows that rule would try the high bits first, and the high-bit rule is the one that pairs coins agreeing in as many leading bits as possible — right on 369 of 1,001 four-coin positions. Welter’s clause moves the decision to the other end of the numbers, and it does so for an arithmetic reason given below: the $-1$ in the animating function reaches down into the trailing bits and nowhere else.

That is the reverse of what the strict mating suggested, too. The mated pairs of the earlier essay, $\{2k, 2k+1\}$, differ only in their last bit, so they are the pairs that agree in the fewest trailing bits. They have animating value nought because $(2k \oplus (2k+1)) - 1 = 0$, and a matching made of them reads nought. But when the low-bit rule is run on a mated position it does not produce those pairs. On the lost position 0, 1, 2, 3, mated as 0–1 and 2–3, it pairs 0 with 2 and 1 with 3, each pair agreeing in its last bit, and reads $\langle 0 \mid 2 \rangle \oplus \langle 1 \mid 3 \rangle = 1 \oplus 1 = 0$ all the same. The mated pairing and the low-bit pairing both read the value, and they are different matchings.

The trie a matching is read from #

The rule is easiest to see as a picture, and the picture is a binary trie drawn upside down: a tree that reads a number’s bits starting from the lowest.

Each coin walks down from the top, going left at a 0 and right at a 1, bit 0 first. Two coins share a path until the lowest bit in which their squares differ, and part there. So the six coins 1, 2, 4, 7, 9 and 11 split at bit 0 into the evens, 2 and 4, and the odds, 1, 7, 9 and 11. The odds split again at bit 1 into 1 and 9, which end in 01, and 7 and 11, which end in 11. And 1 and 9 part only at bit 3, since $1 = 0001$ and $9 = 1001$.

The low-bit matching pairs the coins that stay together longest. 1 and 9 share three bits and are paired first; 7 and 11 share two and are paired next; 2 and 4 are what is left. The three animating values are $\langle 1 \mid 9 \rangle = 8 - 1 = 7$, $\langle 7 \mid 11 \rangle = 12 - 1 = 11$ and $\langle 2 \mid 4 \rangle = 6 - 1 = 5$, and $7 \oplus 11 \oplus 5 = 9$, which is the value of the position.

The same arrangement is a familiar object under another name. “The lowest bit in which two numbers differ” is a distance on the whole numbers, and it has the property of an ultrametric: of any three numbers, the two smallest of their three distances are equal. It is the distance of the 2-adic numbers, in which two numbers are close when their difference is divisible by a high power of two. The low-bit rule pairs the coins that are 2-adically closest. A game about coins on a strip, whose rule is about which squares are occupied, turns out to be governed by a notion of distance under which 1 is nearer to 9 than to 2.

Why two of three matchings always agree #

With four coins the rule has a proof that needs no trie, only one fact about subtraction.

For any $x \geq 1$, subtracting one flips the lowest set bit of $x$ and every zero below it. So

$$\langle a \mid b \rangle = (a \oplus b) - 1 = (a \oplus b) \oplus M_v, \qquad M_v = 2^{v+1} - 1,$$

where $v$ is the lowest bit in which $a$ and $b$ differ. A matching’s value is the exclusive-or of these over its pairs. The $(a \oplus b)$ parts of any perfect matching exclusive-or to the nim-sum of all the squares, whichever matching it is, so matchings differ only in their masks — and a mask depends only on the bit at which the pair parts.

Four coins have three matchings, and each pair of coins lies in exactly one of them. So the closed form, which exclusive-ors all six pairs, is the exclusive-or of the three matchings’ values. The ultrametric property now says that of the three matchings, two always part their pairs at the same bits: on all 1,001 four-coin positions of the first fourteen squares this holds, and it is a theorem, not an observation. Two matchings with the same masks read the same value, those two cancel in the exclusive-or of all three, and the closed form equals the third. The third is the odd one out, and the odd one out is always the one that pairs the two 2-adically closest coins together.

The table shows it row by row. On 0, 1, 2, 4 the matchings 0–1 with 2–4 and 0–2 with 1–4 both part at bits 0 and 1 and read 5; the third, 0–4 with 1–2, parts at bits 2 and 0 and reads 1, the value. On 0, 1, 4, 8, the pair 0 and 8 agree in three trailing bits, and the matching containing it is the one that reads 3.

The proof for any number of coins #

Beyond four coins the matchings multiply — fifteen at six, 105 at eight — and “two of three agree” has no direct analogue. The trie supplies one.

Every pair of coins parts at exactly one node of the trie, and its mask is fixed by that node’s bit. At a node with $l$ coins down one side and $r$ down the other, $l \cdot r$ pairs part there, so the closed form includes that node’s mask $l \cdot r$ times. A mask exclusive-ored with itself an even number of times vanishes. So the closed form’s masks come to one mask for every node where $l$ and $r$ are both odd, and nothing else.

The low-bit matching makes pairs node by node from the bottom of the trie up. Within each side it pairs as many coins as it can, deeper down; a side with an odd number of coins passes one coin up unpaired. At a node, then, it makes a pair exactly when both sides pass a coin up — when both sides are odd — and never otherwise. The table checks this on the six coins: the node at bit 0 has 2 and 4 against 1, 7, 9 and 11, eight parting pairs and no low-bit pair; the three nodes with an odd count each carry exactly one. So the matching includes exactly the masks the closed form keeps, the $(a \oplus b)$ parts agree as before, and the matching reads the closed form’s value. With an odd number of coins the same count leaves one coin unpaired at the top, its square added, and the closed form’s own extra term is exactly that square’s contribution.

One of the lost positions the strict mating misses checks the argument by hand. On 0, 2, 4, 6 the trie splits nothing at bit 0, since all four squares are even. At bit 1 it puts 0 and 4 against 2 and 6: two against two, four pairs parting, an even count and no mask kept. At bit 2 it splits 0 from 4 and 2 from 6, one against one at each of two nodes: two odd nodes, and two masks of $2^3 - 1 = 7$ kept. The low-bit matching pairs 0 with 4 and 2 with 6, one pair at each odd node, and reads $\langle 0 \mid 4 \rangle \oplus \langle 2 \mid 6 \rangle = 3 \oplus 3 = 0$ — lost, as it is. No pair of these squares differs only in its last bit, so there is no mated pairing to find, and the pairing the formula hides had to leave this position among the eight it could not explain.

That is a proof, conditional on the closed form, and the closed form is Conway’s theorem, checked against the recursion here on 3,696 positions. What the proof adds to the earlier reading is the reason a matching exists at all: the closed form is secretly a sum over the trie’s nodes, and a matching can carry one pair per odd node.

The coin left over #

The odd case needs no separate rule, and the trie shows why.

Five coins, 3, 5, 6, 9 and 12. The evens, 6 and 12, part from the odds at bit 0 and from each other at bit 1. Among the odds, 5 and 9 both end in 01 and part only at bit 2, and 3, ending in 11, leaves them at bit 1. The low-bit matching pairs 5 with 9, then 6 with 12, and 3 is what remains. The reading is $\langle 5 \mid 9 \rangle \oplus \langle 6 \mid 12 \rangle \oplus 3 = 11 \oplus 9 \oplus 3 = 1$, the value. The pairing the formula hides found that with three coins the choice of which coin to leave out is forced on every position. The trie says which it is: the coin the counting leaves unpaired as it works up from the bottom.

Unique by rule, not by count #

The earlier essay counted how often only one matching reads the value, and found the share falling as coins were added: 100 per cent at three coins, 29 at six. With the rule in hand that count means something different.

On 790 of the 1,001 four-coin positions the low-bit matching is the only one that reads the value; on 211 another does too. At six coins the split is 360 against 564. The other matchings are not alternative constructions. A matching’s reading depends only on which of its masks survive, and two pairs parting at the same bit have equal masks that cancel — so a matching can arrive at the right total by cancelling masks the closed form keeps. That happens more often as the number of matchings grows, which is the whole of the falling share. The low-bit matching is the one that works by construction; any other that works does so by accident, and “the mating of a position” is best taken to mean the low-bit one.

What the rule does not do #

The earlier essay hoped the matching would turn into a strategy: answer each slide inside the pair it was made in, and keep the reading at nought. For the strict mating on two coins that is exactly right. It is worth checking whether the low-bit matching does the same.

It does not. From every lost position of four coins, every one of the 1,540 moves has a winning reply — the position is lost, so it must — but only 616 of them can be answered by sliding the moved coin’s partner. At six coins it is 384 of 1,224. At three and five coins the moved coin sometimes has no partner at all. So the matching is a certificate of the value and not a recipe for play. The strategy that is a symmetry is about the opposite case, a pairing of moves that is a strategy and names no value, and a pairing that is not a symmetry about a pairing that answers moves without mirroring anything; the low-bit matching is neither, a pairing of coins that answers nothing. A position’s reading is nought exactly when it is lost, and nothing in the reading says which coin to slide when it is not.

The reason is visible in the trie. A slide changes a coin’s square, and a change of square can move the coin to a different branch at any bit. That rearranges the trie, and with it the matching. After a move the low-bit pairs may be quite different pairs from the ones before, so “the pair it was made in” is not a stable thing to answer inside. Nim and the nim-sum has no such problem: its components are the heaps themselves and never regroup, and neither do the coins of a row that is already a sum. Welter’s components regroup with every move.

How the positions were counted #

Every set of two to eight distinct squares below a cap — sixteen squares for two coins, fourteen for three and four, twelve for five and six, eleven for seven and eight — is a position, 3,696 in all. Each is valued by the recursion: a move slides one coin to any lower empty square, and the Grundy value is the mex of the values reached, memoised on the sorted list of squares — the value every impartial game is a Nim heap guarantees exists. The closed form agrees with the recursion on every one. Each rule builds one matching, with a left-over coin whenever the count is odd, and the matching’s reading is compared with the value. The four-coin figures enumerate all three matchings of every position below fourteen squares; the uniqueness counts enumerate all three at four coins and all fifteen at six. The reply counts take every lost position of two to six coins, every legal move from it, and every legal reply.

The convention behind every count #

Normal play: the player who cannot slide a coin loses, and the game ends with the coins packed against the wall. The value is the Grundy value of that game, and the matching reads it. The rule itself depends on writing squares in base two, which is not a convention anybody chose for this game — it is forced by the exclusive-or in the closed form, and it is why the bottom bits, rather than the size of a square or its place on the strip, decide the pairs. Numbering the squares from one instead of nought would change every animating value and every pair, and the rule would have to be restated for the shifted numbers.

What the counts cannot show #

The rule is proved given the closed form, and the closed form is Conway’s theorem, checked here only on the positions counted. The positions stop at eight coins and at small squares, so the trie never goes deeper than four bits, and the proof’s argument is general while its illustrations are not. Ties in the rule — two candidate pairs agreeing in the same number of bits — are broken arbitrarily, and the proof shows the choice cannot matter, since both pair across the same node. And the reply counts measure only one candidate strategy, answering inside the pair. That it fails says the matching is not a strategy, not that no strategy can be read from the trie.

Still open: a strategy read from the trie #

The value is now a sum over the trie’s odd nodes, and a strategy has to say which coin to move to change that sum to nought. In Nim the answer is to find the highest bit of the nim-sum and reduce a heap that has it. The trie suggests an analogue: find the node whose mask sets the highest bit of the reading, and move a coin so that the node’s parity flips — but a slide changes every bit of a coin’s square at once, and so can change the parity of several nodes together. Whether the winning moves from a position of nonzero value can be described by which nodes they flip, and whether the description is as short as Nim’s, is the question the trie now makes askable, on the same 3,696 positions.