One square for every coin

Welter’s game is Nim with one clause added. Coins sit on distinct squares of a strip, a move slides one coin to any lower empty square, and the player who cannot move loses. Read each square as a heap and it is Nim in which no two heaps may be equal — and no two heaps alike found that the clause wrecks the nim-sum completely: the value of a position is not the exclusive-or of the squares on any three-coin position at all. What replaces it is a sum over pairs, and the pairs are read from the bottom bits turned that sum into a sum over the nodes of a binary trie. That is a value. It is not a strategy, and the essay closed by asking for one: which coin to move, and where, to bring the value to nought.

The answer turns out to split cleanly in two, and the split is along a seam Nim’s strategy has but never shows, because in Nim the two halves always come together.

Nim’s strategy is two facts, not one #

The strategy Bouton published for Nim is usually stated as one instruction: find the highest bit of the nim-sum, pick a heap that has it, and reduce that heap to its exclusive-or with the nim-sum. It is really two facts, and they are worth separating.

The first is a fact about each heap separately. Hold every heap but one fixed. Then there is exactly one size for the free heap that makes the nim-sum nought — the nim-sum of the others — and the free heap is a winning move exactly when that target is smaller than it, since heaps only shrink. So there is one target per heap, and the winning moves are the heaps standing above their targets.

The second is a shortcut for finding them. A heap stands above its target exactly when it carries the highest bit of the whole nim-sum, so one number, looked at once, names every winning heap. The count of winning moves is the number of heaps carrying that bit, which is odd, because the bit is set.

Take heaps of 3, 5 and 6, whose nim-sum is 0 and which are therefore lost for the player to move, and change the last to 7. The nim-sum is now 1. The target for the heap of 3 is 5 ⊕ 7 = 2, below it, so reducing it to 2 wins; the target for 5 is 3 ⊕ 7 = 4, below it, so that wins too; the target for 7 is 3 ⊕ 5 = 6, and that wins as well. Three winning moves, and three heaps carry the nim-sum’s only bit, bit 0. The shortcut and the targets agree, because in Nim they are the same computation read two ways.

The first fact is about the shape of the game — how the value responds when one component changes. The second is about the particular arithmetic that value happens to be. Welter’s game changes the arithmetic. The question is whether it keeps the shape.

One target per coin #

It does, entirely. Free one coin, hold the others fixed, and slide the free coin across every empty square.

The first figure shows what this looks like for one position, and the census says it is not a property of that position. As the free coin moves along the strip, the value of the whole position is different on every square — the rows of the first figure have no repeated entry — and it hits nought at exactly one square. Call that square the coin’s target. A coin is a winning move exactly when its target is below it, because coins only slide down; the coin on 0 in any position can never win, whatever its target, for the same reason heap 0 never wins in Nim.

Half of this is not a measurement at all. With the free coin on square b, sliding it down to any empty square b′ below is a legal move, so the position with the coin on b′ is an option of the position with the coin on b — and no position has the same value as one of its options, since the value is the least number not among the options’ values. So the values along a row can never repeat, on any position of any size, and nought can occur at most once. What the census adds is the other half: that nought occurs at all. On every coin tried, it does.

That is Nim’s first fact, word for word, with “heap” replaced by “coin”. It holds on every one of the 18,470 coins and it decides every one of the 3,422 positions: the set of winning moves is the set of coins above their targets, with no exceptions and nothing added.

What it does not yet say is where the target is. In Nim the target is the nim-sum of the other heaps, a number computed from them in one pass. Welter’s game needs a replacement for that sentence.

The target is the value of the others, corrected #

The replacement starts from the value in the form the trie essay gave it. Write the squares in binary and build the trie that reads them from bit 0 upward. The value of a position is the nim-sum of its squares, exclusive-ored with one mask for each node of the trie whose two sides both hold an odd number of coins; the mask for a node at bit v is $2^{v+1} - 1$, the number whose bits 0 to v are all ones.

Now add a coin at square b to a set R of coins. The nim-sum gains b. The trie changes only along b’s own path: every node the path passes gets one more coin on the side b takes. A node’s mask switches on or off exactly when its “both odd” status changes, and adding one coin to one side changes it exactly when the other side holds an odd number of coins. So

value(R with b) = value(R) ⊕ b ⊕ (the masks at the nodes on b’s path where the side b does not take is odd),

and the target is the square b for which b, corrected by those masks, equals the value of the other coins. Nim is the case with no masks, where the target is simply the value of the others — which in Nim is their nim-sum.

The equation mentions b on both sides, and it is solved by walking up the trie. A mask at bit w covers every bit from 0 to w, so bit v of the correction is the parity of the flipping nodes at bit v and above; going up one level, the correction changes exactly when a flip happens. Whether the node at bit v flips depends only on b’s bits up to v. So once b’s bit 0 is chosen, every later bit is forced, one level at a time.

The walk ends when the target’s path leaves the trie — when no other coin shares its low bits. From there nothing can flip, the remaining bits of the target are the remaining bits of the others’ value exclusive-or the correction, and a finite square needs the correction to be nought. Of the two starting choices, exactly one ends on an empty square, on every one of the 18,470 coins. The derivation says each start gives at most one square; that one of them always succeeds and the other always fails is observed on every coin and is not proved here, though it is exactly the statement that the rows of the first figure never repeat.

So the description the trie essay hoped for exists, and its form is instructive. It is not a rule about which node’s parity a move flips; it is a rule for each coin’s target, and the nodes enter as corrections along the target’s own path. The walk is as long as the trie is deep, and it is run once per coin — which is also what Nim costs, if the top-bit shortcut is set aside.

That distribution is why no short formula for the target is hiding behind the walk. A flip at bit v changes every bit of the target from 0 to v, and flips arrive at every level with substantial frequency; a closed expression would have to anticipate where the target’s path goes before knowing the target.

The shortcut does not survive #

Nim’s second fact asks for a single number whose top bit names the winning heaps. The obvious candidate for Welter’s game is the value itself: move a coin carrying its highest bit, to the square coin ⊕ value.

It fails almost everywhere. Across the 3,422 positions of non-zero value, the coins carrying the value’s top bit are exactly the winning coins on 747 — about one in five — and the square coin ⊕ value is the winning square on 1,289 of the 4,908 winning moves. At eight coins the top-bit test is right on four positions of 152. The flips are the reason, again: the target is displaced from the others’ value by masks that depend on where the target lies, so its relation to any one global number is scrambled coin by coin.

The same squares can be a loss in one game and a win three ways in the other. That raises a question the census can answer directly: over all positions, how are the two games’ losses related?

Four coins are Nim #

The answer depends on the number of coins, and it depends on it in a way no reader of the rules would guess.

The four-coin row is not a coincidence of the range; it has a proof that uses nothing about Welter’s value at all.

Take four coins on distinct squares with nim-sum nought — a Nim loss. No move leads to another Nim loss, since Nim has no move between two losses and every Welter move is a Nim move. Now take any four-coin position that is not a Nim loss. Nim’s winning move reduces some heap a to a size x making the nim-sum nought. Could x be a square another coin already holds, which Welter forbids? If x equalled the coin c, the other two coins b and d would need b ⊕ d = x ⊕ c = 0, so b = d, which is impossible on distinct squares. So Nim’s winning move is always a legal Welter move.

Those two facts say the Nim losses form a kernel of Welter’s four-coin game: no move between two of them, and a move into them from everywhere else. A finite game without cycles has exactly one such set — it is the set of losses, built backwards from the end, as working backwards describes — so the Nim losses are the Welter losses. And since the losses coincide and every winning move is a move into a loss, the winning moves coincide as well. On four coins Welter’s clause changes the value of every position and changes the play of none.

At eight coins the argument breaks at its second step — with six other heaps, Nim’s target can land on an occupied square and the rest still cancel — yet the losses agree anyway: of the 3,003 eight-coin positions below fourteen squares, 203 are lost in each game and they are the same 203, and Welter’s winning moves are always among Nim’s. Twelve coins agree on all 91 positions below fourteen squares, seven losses in each game.

The eight-coin row shows what agreement of losses without agreement of moves looks like. When the losses coincide, a Welter winning move is a move into a shared loss, and every such move is a Nim winning move too; what Welter loses are the Nim winning moves that land on an occupied square. Both games have an odd number of winning moves — Nim by its top bit, Welter by the count below — so on every eight-coin position the Nim moves Welter forbids come in pairs. On 32 of the 152 positions of non-zero value there are none, and the two strategies are identical; on the other 120 Welter’s is Nim’s with an even number of moves struck out. That the whole family of multiples of four behaves this way is the obvious conjecture and it is not proved here.

The last bit is a count of pairs #

The disjoint rows have a proof too, and it is the most compact argument in this essay.

Every mask has its last bit set, so the last bit of the correction — the exclusive-or of all the masks — is the parity of the number of trie nodes whose two sides are both odd. A node with l coins down one side and r down the other is where exactly l × r pairs of coins first differ, and l × r is odd exactly when both are. So the parity of the odd-odd nodes is the parity of all the pairs added up: n(n − 1)/2.

A Welter loss has value nought, which means its nim-sum equals its correction; so the last bit of a losing position’s nim-sum is fixed by the number of coins alone. The number of pairs is odd when n is 2 or 3 more than a multiple of four — one pair, three, fifteen, twenty-one, forty-five — and then every Welter loss has an odd nim-sum and cannot be a Nim loss. Two, three, six, seven and ten coins are disjoint for that reason and no other. When the pairs are even, the last bit permits agreement, and whether agreement happens is decided higher up the trie: at four coins always, at five coins on 47 of 189.

The winning moves come in odd numbers #

One more property of Nim survives, and survives without the reason Nim has for it.

In Nim the count is odd because it is the number of heaps carrying a bit that is set in their exclusive-or. Welter’s game has no such bit — the top-bit test has just been seen to fail on four positions in five — and its counts are odd anyway, on every position counted. The row figure at the top is a three; most positions have a single winning move, and five is rare enough to appear only at five and six coins.

The census is evidence and not an argument. It is natural to suspect the oddness comes from the same one-target structure — each coin’s target sits above or below it, and something about the way the targets interleave with the coins forces an odd number below — but no such argument is given here, and the essay records the count as observed.

The conventions behind the counts #

Normal play: the player unable to slide a coin loses. Squares are numbered from nought, and every statement about bits depends on that, since the masks and the trie are read from the squares’ binary digits; numbered from one, every value and every target would change. The censuses are the 3,696 positions of the earlier Welter essays — every set of two to eight distinct squares under caps of sixteen, fourteen, twelve and eleven — each valued by the mex recursion, with the closed form checked against it; the Nim comparison uses the closed form alone, on the larger ranges its figure names. A free coin was tried on every empty square below 64, which is far above any target these positions produce.

What the counts cannot show #

That a coin’s values never repeat is proved above, by the option argument, for every position; that nought is reached at all is checked on 18,470 coins with the free coin below 64 and is not proved here, and neither is the walk’s own version of it — that of the two starting bits one always ends on an empty square. Given that nought is reached, the winning moves being exactly the coins above their targets follows at once. The four-coin equivalence and the disjointness at odd pair counts are proved above and hold on all positions, not only those counted. The agreement at eight and twelve coins, the partial overlap at five and nine, and the odd number of winning moves are observed on bounded squares and could fail beyond them.

Still open: why four is special twice over #

The walk answers the question the trie left, and the census turned up a sharper one. Four coins are the case where Welter’s pairwise value first has three pairings to choose between and where two of the three always agree; they are also the case where the game’s play is Nim’s. Whether those are the same fact — whether the agreement of the losses at every multiple of four follows from the pairing structure the trie makes visible, by grouping coins in fours the way the proof above groups them in twos — is the natural next question, and eight coins, where the losses agree and the moves do not, is where an argument would have to show its hand. The strategy that is a symmetry is the other place in these essays where a pairing turned out to be a strategy, and Sprague–Grundy is why any of this is a question about Nim at all: every impartial position is some Nim heap, and Welter’s game is the rare one where the heap can be named and the moves still have to be found.