The count of odd heaps

The wider move is the easier game tried to describe the losing positions of bounded Moore’s Nim — take up to a fixed amount from up to $k$ heaps — with a two-part statistic built from the heaps’ residues, and refused every version of it. It closed on the object none of the attempts had looked at:

The rung above is the losing set itself. Every rule tried here reads the heaps; nothing has yet looked at the 364 losing positions at $k = 2$ and asked what they have in common as a set … That is the question Bouton answered for Nim with the binary columns, and the shape of the answer there was not a count of anything.

There is such an invariant. It is how many heaps hold an odd number of counters.

Every all-even position is lost #

The clean half of the finding has an argument rather than a count, which is what the rung below was asking for.

A move takes one counter from between one and $k$ heaps, so it changes the parity of between one and $k$ heaps. From an all-even position, whatever the mover does, the opponent can take one counter from exactly the heaps whose parity has just changed — they are non-empty, since they have just been made odd — and the position is all-even again.

The strategy needs somewhere to end, and it has one: the position with every heap empty is itself all-even, and it is the position whose mover loses. So the restoring player never runs out and the position always comes back to them. That is Bouton’s shape exactly — a class closed under move then restore, containing the terminal position — and it holds at every $k$, for the same one-line reason.

It also explains why the rung below’s rules could not find it. Every one of them read the heaps’ residues and combined them arithmetically; this reads a count of heaps with a property, which is a statistic of the multiset and not a function of the residues.

Where the count is the whole answer #

At the two ends of the range the count settles everything.

At $k = 1$ a position is lost exactly when the count of odd heaps is even. That is not a coincidence and it is not new: with one heap touched per move the game is a disjunctive sum of one-heap subtraction games, each heap’s Grundy value is its size modulo two, and the nim-sum of those parities is nought exactly when an even number of them are one. So the invariant at $k = 1$ is Sprague–Grundy applied to five copies of the smallest subtraction game there is.

At $k = 4$ on five heaps it is lost exactly when the count is nought or five — that is, when every heap has the same parity. A move must leave at least one heap alone, so from a uniform position the mover cannot change all five parities and the opponent restores the majority.

Between the two the statistic is partial. At $k = 3$ it settles five of the six classes and 1,652 of the 2,002 positions; at $k = 2$, the case the rung below was working on, four classes and 1,127.

And where it is not #

At $k = 2$ the classes with three and four odd heaps contain both wins and losses — 182 losses among 525 positions and 56 among 350. Between them they hold 875 positions and all 238 of the losing positions the statistic does not account for.

Three is exactly one more than a move can flip, and that is the whole of why the argument stops there. From an all-even position the restoring reply exists because at most two parities have changed; from a three-odd position no move reaches all-even, since flipping three parities takes two moves — but neither can the opponent prevent the mover from working towards it, so the outcome depends on the sizes rather than on the parities.

0, 0, 1, 1, 1 is lost and 0, 1, 1, 1, 2 is won, and they have the same parity profile. The difference is in the sizes, and no statistic here reads it.

The restoring strategy, written out #

The all-even argument is three sentences and it is worth having them in full, because every claim on this page that is a proof rather than a count rests on it.

Claim. In bounded Moore’s Nim with $m = 1$, a position all of whose heaps hold an even number of counters is a loss for the player to move, whatever $k$ is.

The move. Suppose the position is all-even and Left moves, taking one counter from each of a set $T$ of heaps, where $1 \le |T| \le k$. Every heap in $T$ was even and non-empty, so every heap in $T$ is now odd, and no other heap has changed. The position afterwards has exactly $|T|$ odd heaps.

The reply. Right now takes one counter from each heap of $T$. Every heap of $T$ is odd, so every heap of $T$ is non-empty, so the move is legal; and $|T| \le k$, so it is within the width. Afterwards every heap of $T$ is even again and the position is all-even.

The end. Every reply removes $|T| \ge 1$ counters, so the total strictly decreases and the play cannot go on for ever. It ends at a position with no move, which is every heap empty — and that is all-even, so it is Left who is looking at it.

Two things about that are worth noticing. It never mentions $k$ except to check $|T| \le k$, which is why the claim holds at every width; and it never mentions the sizes of the heaps beyond their parity, which is why it says nothing at all about the classes with three odd heaps. A restoring strategy is only ever as strong as the class it restores to.

What kind of answer this is #

The rung below wanted Bouton’s shape, and it is worth being exact about how close this comes.

Bouton’s answer is a complete invariant with a strategy: the nim-sum of the binary columns is nought exactly on the losing positions, and the proof is that a move cannot preserve it and some move always restores it. Two halves, both exact.

What is here is the strategy half, complete, on one class. All even is closed under move-and-restore and contains the terminal position, at every $k$, which is a genuine theorem and not a census. What is not here is the completeness: the class of losing positions is larger than the all-even class at $k = 2$ and $k = 3$, and nothing says what the rest of it is.

That is a familiar half-result rather than a failure, and it has a name in this subject: a P-position class that is provably losing and not provably everything. The theorem that needed none of the theory is the model the anchor keeps failing to reach and it is the model this reaches half of — its invariant is exact where this one is a floor.

The measurement also says where the missing half must live. Two heaps a move on five heaps leaves three classes unaccounted for across the four widths, and every one of them has three or four odd heaps. So whatever completes the description is a statement about positions the parity count cannot move to the all-even class in one turn, and it will have to read the sizes.

Why the two ends are easy #

There is a pattern in which widths are complete, and it is worth naming because it says what the middle is missing.

At $k = 1$ the game decomposes: one heap a move means a sum of independent games, and Sprague–Grundy answers it outright. At $k = 4$ on five heaps the game is almost impartial in one variable: a move must skip a heap, so the position is described by which parity the majority has, and that is a single bit.

The middle widths have neither property. Two heaps a move is too many for decomposition and too few for a majority argument, and it is exactly the regime taking from several heaps at once exists to be about — Moore’s theorem’s whole subject is what happens when a move touches more than one component and less than all of them.

So the difficulty of bounded Moore’s Nim is not spread evenly over $k$. It is concentrated in the middle, and the ends are easy for two different reasons neither of which generalises inward.

What a partial invariant is worth #

There is a temptation to score a partial invariant against a complete one and call it a near miss, and it is worth resisting because the two are used differently.

A complete invariant answers every position and replaces the search. Bouton’s nim-sum does that for Nim: a player who can add binary columns never evaluates anything, and the game is solved in the strongest sense.

A partial invariant answers some positions and shortens the search on the rest. At $k = 2$ the count of odd heaps decides 1,127 of the 2,002 positions outright, and it does it in the time it takes to look at the heaps — so a solver equipped with it can return an answer immediately on 56 per cent of what it is asked and recurse on the remainder. That is worth about what the check in front of a search measures a pairing test to be worth on Cram: not a solution, and a real saving.

And it is worth more than that when the positions it settles are the ones a search would find expensive. Here they are not — an all-even position is as cheap to evaluate as any other — so the honest accounting is that the invariant buys understanding rather than time. What it says is that the losing set is not an unstructured collection of 364 heap multisets: it contains a whole parity class, closed under a strategy, with a proof.

And a partial invariant tells the next rung where to look. The two unsettled classes are 875 positions, completely specified, with 238 losses in them. That is a much smaller and much better posed object than the losing set, which is what the rung below was left with.

A restoring strategy is what an invariant is for #

The all-even result comes with a strategy rather than with a computation, and the difference is what makes it an invariant in the sense Bouton’s rule is one.

A restoring strategy says: the opponent’s move breaks the property, and there is always a reply that restores it. Two things follow immediately and neither needs a search. The property holds after every one of the strategist’s moves, so it holds at the end — and the end is a position with the property, which is a loss for whoever faces it. That is a complete proof of a claim about arbitrarily large positions, obtained from one sentence about a single exchange.

That is the shape every usable result in this subject has — it is exactly the form Bouton’s criterion takes, and it is why the earlier rungs’ failures were failures. A rule that predicts the outcome from a statistic is a rule that has to be checked position by position and holds until a sweep finds a case it does not. A property preserved by a strategy is a theorem, and its evidence is one argument rather than any number of positions.

It also says exactly what the remaining gap is. The all-even positions are covered by a strategy; the classes this page cannot settle are covered by nothing, and finding a rule that predicts them would not be the same kind of result. What is wanted for the rest is another restoring strategy — a property, and a reply that puts it back — and the rung above finds one by widening what counts as the property rather than by widening the sweep.

What this does not say #

The parity classes are not equally sized. There are 126 all-even positions, 350 with one odd heap, 525 with two, 525 with three, 350 with four and 126 with five, which is the binomial profile a multiset of five heaps produces. So a class being settled says nothing on its own about how much of the game it covers, and the coverage figure counts positions rather than classes for that reason.

Five heaps of at most nine. The census is the rung below’s, so the comparison is like for like, and every count here is of 2,002 positions. Whether the parity classes behave the same way on more heaps is not swept, and the $k = 4$ result in particular is about $k$ being one less than the number of heaps rather than about four.

And the amount is bounded at one. The whole page is the $m = 1$ case, where a move takes exactly one counter from each heap it touches. That is what makes parity the natural statistic — with a larger bound a move changes a heap’s residue modulo $m + 1$ rather than its parity, and the analogous statistic would be a count of heaps in each residue class.

The all-even theorem is proved and the rest is measured. The restoring argument is a proof and is checked on 126 positions at four widths; every other statement here is a count over the census, including the completeness at $k = 1$ and $k = 4$, which have arguments sketched and not written out.

And the count is a per-heap statistic aggregated. How many heaps are odd reads each heap and then counts, so it is not as foreign to the rung below’s family of rules as Bouton’s columns are to a count of counters. What makes it different from the rules that failed is that it aggregates by counting heaps rather than by combining residues arithmetically, and the rung below’s family had no member of that shape.

The convention, named #

Normal play throughout: a player who cannot move loses.

Bounded Moore’s Nim at parameters $k$ and $m$: a move chooses between one and $k$ non-empty heaps and takes between one and $m$ counters from each. The whole of this page is $m = 1$, so a move takes exactly one counter from each heap it chooses.

The census is every multiset of five heaps holding at most nine counters each, which is 2,002 positions, and it is the rung below’s population unchanged.

A position is lost when the player to move loses under optimal play, which the evaluator computes by the ordinary backward induction rather than by any rule.

A heap is odd when it holds an odd number of counters; an empty heap is even. The count is how many heaps are odd, and a class is the set of positions sharing that count. A class is settled when all its positions are lost or none is.

Where the ladder goes next #

The moores-nim anchor has five rungs to here, and this one has found the invariant the previous three could not: a statistic of the whole position rather than of any heap.

The rung above finishes it, and the way it finishes is worth knowing because it uses the quantity this anchor spent three rungs ruling out. The parities in size order finds the heap sizes settling the classes this page leaves open — but only through the order they put the parities in. Sort the heaps largest first, read off their parities, and that five-bit word settles the whole game at every width of move, with the losing words forming a subspace.

So the sizes were relevant after all, and every earlier rung was right to refuse them. The refused rules read the sizes as numbers — residues, digits, remainders — and the answer reads them only as a sorting key, which is the one use no arithmetic on them would ever have found.

That is a distinction worth carrying past this game. A quantity can enter an answer as a value or as an ordering, and a search over rules that compute with it will never discover the second. The sizes decide which parity goes where, and nothing about their magnitudes matters beyond that — which is why the losing set is a subspace of a five-bit space rather than a condition on numbers.