The parities, in size order

The count of odd heaps found that counting how many heaps are odd settles bounded Moore’s Nim completely at the ends of the range and partly in the middle, and closed on the largest class it could not settle:

The rung above is the three-odd class. It is 525 positions at $k = 2$ with 182 losses in it, entirely in hand, and it is the smallest completely specified thing this anchor has ever had left over. The question is whether the losing ones are picked out by something about the sizes — the smallest heap, the total, the number of empty heaps — once the parities are held fixed.

They are. None of those three is it, and what is turns out to make the whole ladder’s previous answer a special case.

Sort the heaps and read the parities #

The invariant is one line. Sort the heaps into decreasing order and write down their parities. Five heaps give a five-bit word, and that word settles the game.

Every one of the 32 words is uniform: every position carrying it loses, or every position carrying it wins, over all 2,002 positions of five heaps to nine counters. There is no residue, no exception class, and nothing left over.

At $k = 2$ four words lose — $00000$, $11100$, $01111$ and $10011$ — holding 126, 126, 56 and 56 positions. That is 364 in total, which is the rung below’s count of losing positions exactly, arrived at from the other side.

The order is what the sizes contribute #

The rung below’s statistic is the number of odd heaps, which is the weight of the word. Group the words by weight and the reason it could not finish is immediate: at weight three, $11100$ loses and $00111$ wins, and at weight four, $01111$ loses and $10111$ wins.

Both members of each pair have the same multiset of parities and different verdicts, so no function of how many heaps are odd can decide. What separates them is where the odd heaps sit in the size order: $11100$ is the three largest heaps are odd, and $00111$ is the three smallest are.

So the sizes do enter, and only in that way. The magnitudes themselves — the smallest heap, the total, the number of empty heaps, the nim-sum — all fail: on the three-odd class the nim-sum settles not one of its eight values, and the total settles two positions out of 525. The wider move is the easier game is where a family of two-part rules reading the heaps was tried and refused, and the refusal now has an explanation rather than only a count. What the sizes do is order the parities, and once they have done that nothing else about them matters.

That is a real answer to the rung below’s question and not the one it framed. It looked for a statistic of the sizes to sit alongside the parity count; what the sizes supply is not a statistic but a permutation.

Complete at every width #

The word is not a patch for $k = 2$. It settles the game at $k = 1$, $2$, $3$ and $4$ — all 32 words uniform at every width, on all 2,002 positions.

And it contains the previous answers rather than replacing them. At $k = 1$ the 16 losing words are exactly the even-weight ones, which is the count of odd heaps is even — the disjunctive-sum theorem the rung below identified. At $k = 4$ the two losing words are $00000$ and $11111$, which is every heap has the same parity. Both are functions of the weight alone, which is why the count sufficed there; at $k = 2$ and $k = 3$ they are not, which is why it did not.

So the ladder’s three previous findings are three readings of one invariant, at the widths where the invariant happens to be weight-only.

The losing words are a subspace #

The losing words are not a list. At every width they contain the all-zero word and the exclusive-or of any two of their members, so they form a linear subspace of the five-bit words — dimension 4 at $k = 1$, 2 at $k = 2$, and 1 at $k = 3$ and $k = 4$.

At $k = 2$ that is visible by eye: $11100 \oplus 10011 = 01111$, and the three of them with the all-zero word are a group of order four.

This is the shape the rung two below was reaching for when it said the shape of the answer there was not a count of anything. Nim and the nim-sum is Bouton’s theorem, and Bouton’s losing set is the kernel of a map into $\mathbb{F}_2^k$ — a subspace, not a count. Bounded Moore’s Nim’s losing set is a subspace too, of a different space: the parities in size order rather than the binary columns.

What is missing is the map. Bouton’s kernel comes with a function — the nim-sum — whose vanishing defines it; here the subspace is exhibited by its four members and nothing says what linear condition they satisfy. A basis is $11100$ and $10011$, so the losing words are the ones orthogonal to some pair of vectors, and finding that pair is a small piece of linear algebra over $\mathbb{F}_2$ that would turn the table into a formula.

Where it stops #

The invariant is not general, and the boundary is not where a reader would look for it.

Raising the heap cap changes nothing. Five heaps to eleven counters is 4,368 positions and every word is uniform; to thirteen is 8,568 and every word is uniform. The word does not care how large the heaps are.

A sixth heap breaks it. On six heaps of at most seven counters, 33 of the 64 words are uniform and 792 of 1,716 positions are covered. The word $111000$ holds 84 positions and 76 of them lose — a majority, not a verdict.

So the boundary is in the number of heaps rather than in their size, which is the opposite of the usual shape. A reader expecting an invariant to fail as the game gets bigger would expect it to fail when the heaps grow, and it does not.

An invariant that reads a position twice #

It is worth stopping on the kind of invariant this is, because the site has not met one quite like it.

Most invariants on these ladders are functions of a position’s parts, combined by something commutative — a nim-sum, a count, a total, a maximum. Every one of those ignores the order the parts are written in, and that is usually a virtue: a Nim position is a multiset, so an invariant that noticed the order would be noticing something the game does not.

This one notices the order and the game does not. Bounded Moore’s Nim is a game on a multiset of heaps: relabelling them changes nothing. So the parity word cannot be the invariant in the sense a nim-sum is; it is a canonical reading of the position — sort, then look — and the sorting is a choice made by the reader rather than a feature of the game.

What that means is that the word compresses two different facts into one object. The parities are a fact about the heaps; the size order is a second fact, about which heaps are large. A position is lost when those two facts are in a particular relation, and the word is the cheapest way of writing the relation down.

That reading also explains why the rung below’s statistic got so far and no further. Counting the odd heaps keeps the first fact and discards the second — and the second is what separates $11100$ from $00111$. The rule a smaller move breaks is the anchor’s record of the same loss one rung earlier, where a residue rule kept the sizes and discarded the parities, and got exactly as far in the other direction.

The two facts are not symmetric, though, and the asymmetry is worth noticing. Once the parities are known in order, the actual sizes are irrelevant — a $9, 7, 5, 4, 2$ and a $3, 3, 1, 2, 0$ are the same word and the same verdict, and they are not remotely the same position. So the game’s whole content, on five heaps, is five bits.

Why a sixth heap should be different #

There is a reading of the boundary, and it is the same argument the rung below used for the all-even class.

The restoring strategy behind every result on this anchor is that a move changes the parity of between one and $k$ heaps, and the loser answers by changing them back. With five heaps and $k = 2$, a move touching two heaps leaves three untouched, and three is more than half — so the position after the move is constrained in a way the answering player can exploit.

With six heaps a move of width two leaves four untouched, which is a smaller share, and the mover has more room to change the size order without changing which heaps are odd. Since the invariant reads the size order, a move that reorders the heaps without changing their parities moves between words — and the more room a mover has to do that, the less the word can constrain them.

That is a reading and not an argument, and it makes one prediction that has not been tested: the word should hold at six heaps for larger $k$, where a move touches more of the board and less is left free to be reordered. Nothing here checks it.

Five bits, and what a player does with them #

The result has a practical form and it is short enough to state as advice.

A player facing a bounded Moore’s Nim position with five heaps and moves of width two puts the heaps in order, largest first, and reads their parities. If the word is $00000$, $11100$, $01111$ or $10011$ they are in trouble; anything else and there is a winning move.

Finding the move is a separate matter and this page does not supply one. What the word gives is the verdict, which is what a P-position characterisation always gives — nim is easy is the site’s standing observation that knowing the losing set and knowing the move are usually the same problem for an impartial game, because a winning move is a move into the losing set, and here that is a search over the moves rather than a formula.

There is one shortcut the subspace structure does offer. Because the losing words form a group under exclusive-or, the difference between the current word and a losing one is itself a word — and a move changes at most $k$ of the bits, so a position is a win exactly when some losing word differs from it in at most two positions and the reordering caused by the move is consistent. The second clause is the hard half and is where the size order stops being free.

A subspace is a stronger finding than a rule #

The losing words forming a subspace is reported alongside the rule and it is the more informative half. It is worth saying what it adds.

A rule that settles every position is a lookup: thirty-two five-bit words, each labelled won or lost, and a table serves it. That is complete and it is inert — it says which words lose and nothing about why those words.

A subspace is a structure. It says the losing set is closed under exclusive-or: the sum of two losing words is a losing word, nought is one, and the whole set is generated by a handful of basis elements. So the table is not thirty-two independent facts but a couple of generators and linearity.

That is the same shape Bouton’s criterion has, and the resemblance is the point. Nim’s losing positions are the kernel of a linear map over the binary digits, and finding a linear structure in a bounded variant’s parity words says the two games are related in the way the analysis wants rather than merely in the way the rules look.

It also says what to try next on a variant nobody has settled. Compute the losing set, write it in whatever coordinates the rule suggests, and test for linearity — because a losing set that is a subspace has a basis, a basis is a handful of positions, and a handful of positions is a description a reader can carry. A losing set with no structure is a table, and a table is where an analysis stops rather than where it arrives.

What this does not say #

The population is small heaps. Nine counters, eleven and thirteen are all the caps swept, and every one of them settles. That is three points and the invariant plainly does not depend on the cap, but nothing here evaluates a heap of fifty.

The subspace has no formula. What is measured is that the losing words are closed under exclusive-or at four widths. The linear condition defining them is not identified, and until it is, subspace is a description of a table of four words rather than a theorem.

The bound on the amount is one. Every position here is bounded Moore’s Nim with at most one counter taken from each heap, which is the rung below’s game and the one its 364 comes from. A larger bound is a different game and nothing here speaks to it.

And the six-heap failure is one shape. Six heaps to seven counters is the largest six-heap sweep affordable, and the failure is measured at $k = 2$ only. Whether it also fails at $k = 3$, and whether seven heaps fails worse, is unmeasured.

The convention, named #

Normal play throughout: the player who cannot move loses.

Moore’s Nim with parameter $k$ lets a player take from between one and $k$ heaps in a single move. It is bounded here at one counter a heap, so a move is a choice of at most $k$ non-empty heaps, each of which loses exactly one counter. That is the rung below’s game unchanged.

A position is a multiset of five heap sizes, each from nought to nine, so the population is 2,002 positions counted once each however many orders they could be written in.

The parity word of a position is its heaps sorted into decreasing order with each replaced by its parity — $1$ for odd, $0$ for even. A word is uniform when every position carrying it has the same verdict.

Closed under exclusive-or means the set of losing words contains the all-zero word and, for any two of its members, their bitwise exclusive-or. A set of binary words with that property is a linear subspace, and its dimension is the logarithm of its size.

Where the ladder goes next #

The moores-nim anchor has six rungs: taking from several heaps at once, the rule a smaller move breaks, the patch that generalised, the wider move is the easier game, the count of odd heaps, and now the word the sizes make of them.

The rung above is the linear condition. The losing words are a subspace at every width and no map is known whose kernel they are; a basis at $k = 2$ is $11100$ and $10011$, so the condition is two linear equations over $\mathbb{F}_2$ in five variables and finding them is an exercise rather than a sweep. What would make it worth more than an exercise is the same computation at four and six heaps: if the conditions at three, four and five heaps are one family with the heap count as a parameter, the family is a theorem in waiting, and it would say what a sixth heap breaks.

Two neighbours are worth the trip. Nim and the nim-sum is Bouton’s theorem, which is the answer this page’s answer is shaped like — a kernel rather than a count — and reading the two together is the clearest statement of what an impartial game’s losing set usually looks like. And taking from several heaps at once is where Moore’s rule arrives and where the unbounded version’s answer is stated, which is a count of residues and is what this bounded game keeps failing to have. The patch that generalised is the one repair on this anchor that did survive, and it is worth reading beside a result that needed no patch at all.