No two heaps alike

Coins on a strip of squares numbered from zero. A move slides one coin to any lower square that is empty; a coin may jump over other coins but two coins may never share a square. That last clause is the only difference from Nim written on a strip. Normal play, so the game ends when the coins are packed against the wall at the left and whoever cannot move has lost.

Read each coin’s square number as a heap of that many counters and this is Nim, with one clause added: no two heaps the same size. The clause looks like a restriction on an otherwise familiar game.

Why the nim-sum stops working #

Nim’s whole theory is that the heaps are independent. A move in one leaves the others exactly as they were, so the position is a disjunctive sum and its value is the nim-sum of the parts.

Here they are not independent. A coin cannot move to a square another coin occupies, so what one coin may do depends on where the others are. That is the definition of a component being interfered with, and once it happens the value of the whole is not a function of the values of the parts.

The census makes the size of the failure clear. Over 523 positions with one to six coins, the nim-sum gives the Grundy value 84 times — and every one of those 84 is either a single coin, where there is nothing to interfere, or one of the accidental agreements among four- and five-coin positions. Among the 55 two-coin positions and the 120 three-coin positions it is right exactly zero times.

What is right instead, for two coins #

Two coins on squares $a$ and $b$. The Grundy value is

$$\langle a \mid b\rangle \;=\; (a \oplus b) - 1$$

— the nim-sum of the two squares, minus one. It is exact on all 55 two-coin positions inside the first eleven squares, and the minus one is not a fudge.

Where the minus one comes from is easiest to see at the bottom. The value is zero exactly when $a \oplus b = 1$, which for two distinct squares means the pair is $\{0,1\}$, $\{2,3\}$, $\{4,5\}$ and so on — the squares paired off two by two.

The picture behind the pairing is the reason the function is called animating in the literature and the pairs are called mates. Two coins on mated squares are locked together: whatever one player does with one of them, the opponent can restore the mating with the other, and the restoration is always available because the mate of a square is a square.

The strategy behind the minus one #

The mating is worth making concrete, because it is the one place in this game where a reader can win without evaluating anything.

Every square has a mate: the square reached by flipping its bottom bit. Zero mates with one, two with three, four with five, and the whole strip falls into these pairs with nothing left over. The two-coin positions worth zero are exactly the ones whose coins sit on a mated pair, which is what the picture above shows without any arithmetic.

The generalisation is that a position whose occupied squares are a union of complete mate-pairs is worth zero, however many coins there are. $\{0,1,4,5\}$ is such a position; so is $\{2,3,8,9,10,11\}$. Over every position of that shape inside the drawn strip the recursion returns zero without exception, and the reason is a strategy rather than a formula.

The strategy is: restore the mating. Whatever the opponent does — and a move always breaks exactly one pair, since it lifts one coin off its mate and drops it somewhere else — reply so that the occupied squares are once again a union of complete pairs. The usual reply is the mirror of the opponent’s own move, taking the mate of the coin they moved to the mate of the square they moved it to, and it is available for the same reason the mating exists at all: the mate of a square is a square, and it is a square on the same side of the strip.

The claim that such a reply always exists is not obvious and is checked rather than asserted. Over every complete-pair position in the strip, every legal opponent move was generated — six hundred and sixty of them — and every single one has at least one reply landing back in a complete-pair position. So the second player never runs out of mirror, and the position is a second-player win by an argument a person can carry in their head.

Where the mirror runs out #

That would be a tidy end to the story if the mating characterised the losses, and it does not. It is sufficient and it is not necessary, and the gap is where the closed form earns its keep.

$\{0, 2, 4, 6\}$ is worth zero. It contains no mated pair at all — every coin sits on an even square and every mate is odd and empty — so nothing the previous section describes applies to it, and yet the mover loses.

The sweep says how large the gap is, and it is most of the territory. Inside this strip there are 113 zero-valued positions with an even number of coins. Forty-one of them are unions of complete mate-pairs and the mirror strategy wins those; the other seventy-two are not, so the strategy has nothing to say about them, and twenty-four of those contain no mated pair whatever.

Run the formula on it and the answer falls out in six terms. The pairs give $\langle 0\mid 2\rangle = 1$, $\langle 0 \mid 4 \rangle = 3$, $\langle 0 \mid 6 \rangle = 5$, $\langle 2 \mid 4 \rangle = 5$, $\langle 2 \mid 6 \rangle = 3$ and $\langle 4 \mid 6 \rangle = 1$; nim-added they cancel in pairs and leave zero, and the number of coins is even so nothing is added back. No mirror, no visible symmetry, no packing against the wall — just three cancellations.

That is the honest division between the two accounts. The mating gives a strategy and covers a thin slice of the losing positions; the formula gives a number and covers all of them, and gives no strategy whatever. A reader who wants to win $\{0,1,4,5\}$ has a rule they can follow. A reader who wants to know that $\{0,2,4,6\}$ is lost has an evaluation and no story, and would have to search for the moves that make it stick.

The site’s usual preference is for the account that explains, and this is one of the cases where the explaining account is the weaker one. It is worth saying plainly rather than choosing between them: mating is why the minus one is in the function, and the function is why the mating is not the whole answer.

The rule for the whole board, and its condition #

The interesting part is what happens with more than two coins. The natural guess is that a function of pairs composes: work out $\langle a \mid b \rangle$ for every pair of coins and nim-add the results.

So the guess is right, and it is right only when the number of coins is even. With an odd number the pairwise sum is wrong nearly everywhere, and the repair is a single extra term:

$$G(a_1, \ldots, a_n) \;=\; \bigoplus_{i<j} \langle a_i \mid a_j\rangle \;\oplus\; \begin{cases} a_1 \oplus \cdots \oplus a_n & n \text{ odd} \\ 0 & n \text{ even}\end{cases}$$

Checked against the recursion on 523 positions with one to six coins, it is right on every one.

Why parity should be involved at all #

The parity clause is the surprise, and once the arithmetic is written out it is not a surprise at all — which is the satisfying part.

Expand $\langle a_i \mid a_j \rangle = (a_i \oplus a_j) - 1$ and think of the nim-sum over all pairs. Each coin $a_i$ appears in exactly $n - 1$ pairs, so in the term $\bigoplus_{i<j}(a_i \oplus a_j)$ each coin’s square is xored in $n-1$ times. Xoring a value an even number of times cancels it; an odd number of times leaves one copy. So for $n$ odd the pairwise sum has already contributed each square once over, and for $n$ even it has contributed nothing.

That accounts for the direction of the correction but not its exact form, because the minus ones interact with the borrowing in a way that does not decompose cleanly. What the sweep establishes is that whatever the interaction does, the result is exactly the plain nim-sum of the squares — no more and no less — and that it is needed for odd $n$ and absent for even.

Checking a formula against a search #

There is a habit worth making explicit here, because this is one of the few essays on the site where a closed form is the finding rather than a census.

A formula found by looking at data is a conjecture. It becomes a claim when it is evaluated on positions it was not fitted to, and it becomes a fact about this site when the evaluation is run beside a search that does not use it. Both halves are computed here: the recursion builds the option set of each position, takes the mex, and never sees the formula; the formula is evaluated from the square numbers, and never sees the recursion.

The search side of that check is one line of arithmetic repeated: the value of a position is the minimum excludant of its options’ values — the smallest non-negative integer none of them carries — and the option list comes from sliding each coin to each lower empty square. Nothing in it mentions pairs, minus ones or parities, which is what makes the agreement worth reporting rather than circular.

The check that could have failed is not the agreement — it is the parity split. A formula that agreed on the even cases and was silently applied only there would have proved nothing about composition; the odd rows are in the table with their low numbers printed, so the failure is visible rather than excluded.

The one-coin case, and why it is not trivial #

A single coin on square $a$ is a heap of $a$ counters with nothing to interfere with it, so its value should be $\ast a$ and it is: all twelve one-coin positions agree with the nim-sum, which for a single number is the number itself.

That row is in the census as a control. A formula that failed there would be a formula that had gone wrong in its simplest case, and the pairwise term contributes nothing when there are no pairs — so the one-coin row is testing exactly the correction term, and it is the row where the parity clause first earns its place: one coin is an odd number of coins, the pairwise sum is empty, and the whole value comes from the term the even case does not have.

That is a small thing and it is the kind of small thing that catches an error. A formula stated as “nim-add the pairs” without the parity clause would give zero for every single-coin position, which is wrong for eleven of the twelve, and the mistake would be invisible to anybody who checked only the two-coin case.

Where the moves are #

The formula gives the value and a value gives the outcome, and neither gives the move. For that a player still needs the option list, and the option list is where the interference lives.

That is the standing division of labour in this subject. Sprague–Grundy tells a player which positions are lost and Welter’s function tells them the number without a search; finding a move still means looking at options, and the formula’s contribution is that it makes each option’s value cheap to evaluate rather than making the list unnecessary.

What the game is a disguise for #

A Welter position is a set of distinct non-negative integers, and there is another name for that: a partition into distinct parts. Sliding a coin down is replacing one part by a smaller one not already present, which is the natural move on such a partition, and the game is the reachability structure of that operation.

That is worth knowing because it explains where the difficulty is. A partition into distinct parts is not a bag of independent numbers — the distinctness is a global constraint, tying every part to every other — and a global constraint is exactly what a disjunctive sum cannot express. So the failure of the nim-sum here is not a quirk of the strip; it is the constraint refusing to decompose, and the pairwise function is what a constraint between two things looks like when it is written down.

The same shape appears elsewhere on this site whenever a rule reaches across components. An entailing move does it by compelling a reply in a named component; the “no two alike” clause does it by making one component’s options depend on another’s position. Both break the sum theory, and Welter’s game is the case where something exact survives the break.

Who found it, and when #

Welter published the game and its solution in 1954, in a paper about a problem in the theory of partitions rather than about games — the strip of coins is a way of writing a partition into distinct parts, and moving a coin down is a way of modifying one.

Conway’s account in On Numbers and Games is the one that gives the animating function its name and works out the structure behind the parity clause, in a chapter that goes on to build the whole apparatus of “mating” for games of this shape. The reading here is neither of theirs: the formula is evaluated and compared with a mex, and what is reported is that the two agree on 523 positions.

What a player would actually do with it #

A closed form is worth having when it changes what a person can do at the board, and this one does, in a way worth spelling out.

Without it, deciding a six-coin position means a search: build the option list, evaluate each option, take the mex, and the option lists are long because a coin near the top of the strip can drop to any of a dozen squares. The work grows with the strip.

With it, deciding the same position is fifteen exclusive-ors and a parity check. Finding a move still means scanning the options — but each option is now a formula evaluation rather than a subsearch, so the scan is linear in the number of moves rather than exponential in the depth.

That is the ordinary payoff of a closed form and it is the reason the subject looks for them. What is unusual here is how narrow the form’s licence is: it is exact, it is cheap, and it applies to precisely one game. Nothing about it survives a change to the rules, which is the opposite of the situation with the nim-sum, whose whole point is that it applies to everything impartial at once.

Where the model stops #

Six coins and squares below twelve. That is 523 positions, which is enough for a formula agreeing everywhere to be worth stating and is not a proof. The parity clause in particular is a claim about how the formula behaves as $n$ grows, and $n$ here goes to six.

The formula is also silent about a natural generalisation. Welter’s game with the coins on a two-dimensional board, or with the “no two alike” clause weakened to “no three alike”, are games this page says nothing about, and there is no reason to expect the pairwise structure to survive either.

And the game itself is a boundary case of something larger. Every impartial game is a Nim heap, so Welter’s game is a sum of nothing — one position with one Grundy value — and calling the coins “heaps” is a description of the picture rather than a decomposition of the game. The whole content of this page is that the picture’s obvious decomposition is not the game’s.

Where the ladder goes next #

This rung establishes the closed form and its parity condition. The rung above is the structure behind it: why a function of pairs should describe a game at all, which is Conway’s mating theory and is a construction rather than a formula.

Two neighbours are worth the trip. The move that gives counters back is the other essay here about a clause added to Nim, and the contrast is sharp — there the clause changes nothing and here it changes everything. And a row of coins is already a sum is the other game on this site whose position is coins on a strip, where the decomposition the picture suggests turns out to be the right one.