Maundy Cake

A rectangular cake scored into unit squares. Left cuts along a vertical scoring line, all the way through; Right cuts along a horizontal one; whoever cannot cut loses. That is Cutcake, and the surprising thing about it is how unsurprising its answers are: every value is a plain whole number, and the number is a count of spare moves.

Maundy Cake is the same cake with one word added. A cut must divide the piece into equal parts. Left may cut an $m \times n$ cake into three $m \times (n/3)$ cakes if three divides $n$, or into two halves if two does, but not into a piece of four columns and a piece of five. Every piece stays on the table and stays in play. Nothing else changes — same board, same alternation, same losing condition.

The values are still integers, so the game is still cold: neither player ever gains by cutting, nothing is ever at stake, and the number is a count of moves in hand. But the arithmetic that decides that number is not Cutcake’s, and the account of it this site has been carrying is wrong.

The game it is a variant of #

Cutcake’s answer is about binary digits. An $m \times n$ cake is worth nothing exactly when $\lfloor \log_2 m \rfloor = \lfloor \log_2 n \rfloor$ — when the two dimensions have the same binary length — which puts the zeros of the table into square blocks of doubling size: the single cell $1\times1$, then the $2$-to-$3$ square, then the $4$-to-$7$ square, then the $8$-to-$15$ square.

That rule was checked here over all 576 cakes to $24 \times 24$ and holds without exception, and so does the closed form that goes with it: for $m \le n$, with $a = \lfloor \log_2 m \rfloor$ and $b = \lfloor \log_2 n \rfloor$, the cake is worth $\lfloor n/2^a \rfloor - \lfloor n/2^b \rfloor$, the rest of the table following by antisymmetry. The mechanism is a count of halvings and the value is a count of spare moves: the binary length is how often a dimension can be halved before reaching one, and the player with more halvings in hand has moves left when the other has none.

Maundy Cake changes which cuts exist rather than merely how many. Cutcake’s Left, on a cake twelve columns wide, has eleven cuts; Maundy Cake’s Left has five, one for each way of writing twelve as a number of equal parts greater than one. The change looks like a restriction and behaves like a substitution: a game organised by halving in, a game organised by factorising out.

The claim, and three ways of reading it #

The Cutcake essay names Maundy Cake as its generalisation, and until this census was run it reported that its values are integers and that the count involves the largest odd divisor rather than the binary length. That is the received summary of the game, a reader may well have met it there, and it is false. The sentence has since been corrected on the strength of what follows.

It is also imprecise, so it was tested in every reading that could be made of it, by exhaustive search against a solver that computes Maundy values from the moves and knows nothing about divisors. Write $\mathrm{od}(k)$ for the largest odd divisor of $k$, so that $k/\mathrm{od}(k)$ is the largest power of two dividing $k$. Over all 1,296 cakes to $36 \times 36$:

• The value is $n/\mathrm{od}(n) - m/\mathrm{od}(m)$. 946 counterexamples out of 1,296. The first is the $1 \times 3$ cake, which the rule makes worth 0 and which is worth 1.
• The cake is worth zero exactly when $\mathrm{od}(m) = \mathrm{od}(n)$. 382 counterexamples. The first is the $1 \times 2$ cake: the odd parts agree, and the cake is worth 1.
• The value is $\Omega(n) - \Omega(m)$, counting prime factors with multiplicity — the reading that keeps the shape of the claim and swaps the arithmetic function. 408 counterexamples. The first is $1 \times 4$, worth 3 where the rule says 2.

The $1 \times 3$ cake is the whole refutation in one cell, and small enough to check by hand. Under Maundy Cake, Left’s only legal cut of a strip three squares long is into three $1 \times 1$ cakes, each worth nothing, so Left’s single option is $0$; Right has no cut at all; the value is $\{0 \mid \ \} = 1$. Under Cutcake, Left may also cut it into a $1 \times 1$ and a $1 \times 2$, worth $0 + 1 = 1$, so the value is $\{1 \mid \ \} = 2$. Every version of the odd-divisor claim has $3$ and $1$ sharing an odd part and therefore predicts a balanced cake, and the cake is not balanced: it is a win for Left by one move, whoever goes first.

What survives is a count of prime factors #

What the exhaustive computation supports, without a single exception over the 1,296 cakes, is a rule about $\Omega(k)$ — the number of prime factors of $k$ counted with multiplicity, so that $\Omega(1) = 0$, $\Omega(12) = 3$ and $\Omega(16) = 4$:

• the $m \times n$ Maundy cake is worth zero exactly when $\Omega(m) = \Omega(n)$, and
• the sign of the value is the sign of $\Omega(n) - \Omega(m)$.

The mechanism is the same shape as Cutcake’s with a different operation inside it. A Maundy cut of the $n$-side into $j$ equal pieces replaces $n$ by $n/j$, and $\Omega(n/j) = \Omega(n) - \Omega(j)$, at most $\Omega(n) - 1$ and exactly that when $j$ is prime. Each cut spends at least one of the $n$-side’s prime factors, so no line of play cuts the $n$-side more than $\Omega(n)$ times: Left’s supply of cuts, measured in depth, is $\Omega(n)$ and Right’s is $\Omega(m)$, and the player with more still has somewhere to cut after the other has run out.

Cutcake counts the same thing over a smaller alphabet. $\lfloor \log_2 n \rfloor$ is how long a chain of halvings $n$ admits; $\Omega(n)$ is how long a chain of divisions by primes it admits. One game lets a player divide only by two, the other by anything, and both turn out to be about the length of the resulting chain — which is how a rectangle with no arithmetic in its rules produces a table organised by number theory twice over, by two different pieces of it, from rules a word apart.

The rule also explains the row that looks most irregular. $1 \times n$ is worth 1 for every prime $n$ — 2, 3, 5, 7, 11 and 13 all give 1 — because the only equal cut of a prime strip is into unit squares, and the value is $\{0 \mid \ \} = 1$ however long the strip. A strip of thirteen squares and a strip of two are worth the same one spare move.

Who wins is not by how much #

The Ω rule is a complete account of the outcome over the range computed, and it is emphatically not an account of the value. The temptation to promote it is strong and the numbers refuse.

Take the four cakes $1 \times 8$, $1 \times 12$, $1 \times 18$ and $1 \times 20$. All four have $\Omega(n) = 3$ against $\Omega(m) = 0$; all four are wins for Left by the rule above; and they are worth 7, 10, 13 and 16. Four positions the rule cannot distinguish, four different values, a spread of nine moves. Nor is the difference explained by rescaling: $2 \times 8$, $2 \times 12$ and $2 \times 20$ have the same three counts against one and are worth 3, 4 and 6.

The reason is in the cut. A Maundy cut into $j$ pieces does not leave one position behind, it leaves $j$ of them, and the option is worth $j$ times the value of a single piece — so the size of the factors matters and not only how many there are. $\Omega$ throws that away by construction, being a length. What does give the size is the simplicity rule, and it is the same rule that gives Cutcake its integers.

What the solver computed, and how #

An $m \times n$ Maundy cake is built as a game whose Left options are, for each divisor $j > 1$ of $n$, the disjunctive sum of $j$ copies of the $m \times (n/j)$ cake, and whose Right options are the corresponding sums for divisors of $m$. Nothing in that construction mentions integers, primes or divisor counts. The value comes back from the ordinary canonical-form machinery, and the generator then refuses to draw a cake whose name is not a plain integer, so a single fraction or star in a table would fail the build rather than appear in it.

Where both players’ best options are numbers and Left’s lies below Right’s, the value is the simplest number strictly between them — simplest meaning born earliest, so an integer beats a half and a half beats a quarter. Three cakes, worked:

• $2 \times 4$. Left’s best cut is into two $2 \times 2$ cakes, each worth 0, for an option of 0. Right’s best cut is into two $1 \times 4$ cakes, each worth 3, for 6. The simplest number strictly between 0 and 6 is 1.
• $4 \times 6$. The two bounds are $-2$ and $2$, and the simplest number between them is 0 — which is also what the prime-factor rule says, since $\Omega(4) = \Omega(6) = 2$.
• $2 \times 12$. Left’s best cut is into three $2 \times 4$ cakes, worth 3 in total, beating the halving into two $2 \times 6$ cakes at 2. Right’s cut gives 20. The simplest number strictly between 3 and 20 is 4.

Two of the three are not midpoints, which is the whole content of the rule and the reason a reader cannot recover the table by averaging. The strips with no Right cut at all are starker still: $1 \times 12$ has Left’s best option at 9 — three $1 \times 4$ cakes at 3 each, beating two $1 \times 6$ cakes at 4 each — and no Right option whatever, so the bound is $(9, \infty)$ and the value is 10. $1 \times 8$ has bound $(6, \infty)$ and comes out at 7.

Two rules that draw the same number of draws #

The two games are close on small cakes and part company fast. Up to $4 \times 4$ they disagree about exactly one cake and its mirror image — the $1 \times 3$ — and about nothing else among the sixteen. By $6 \times 6$ they disagree on 18 of 36, by $8 \times 8$ on 32 of 64, and by $12 \times 12$ on 96 of 144.

Now the coincidence. Out to $24 \times 24$ there are 576 cakes, and each game is worth zero on exactly 166 of them — and only 58 are the same cake. Two rules that share no vocabulary, applied to the same 576 rectangles, produce the same number of balanced positions and disagree about two thirds of which ones they are.

The equality is an accident of where the count stops, and the arithmetic behind it shows exactly what kind of accident. Both rules partition $\{1, \dots, 24\}$ into classes and call a cake balanced when its two dimensions fall in the same class. Cutcake’s classes are the binary bands $\{1\}$, $\{2,3\}$, $\{4..7\}$, $\{8..15\}$, $\{16..24\}$, of sizes 1, 2, 4, 8, 9. Maundy Cake’s are the numbers with a given count of prime factors: one number with none, nine primes, eight with two factors, four with three, two with four — sizes 1, 9, 8, 4, 2. The count of balanced cakes is the sum of the squares of the class sizes, and the two lists are the same five numbers in opposite order: $1 + 4 + 16 + 64 + 81$ and $1 + 81 + 64 + 16 + 4$ are both 166.

Nothing forces that. One list is governed by powers of two and the other by how many integers up to the bound have exactly $k$ prime factors, and at a bound of 24 they happen to be reverses of one another. It is a coincidence with a completely explicit cause, and it is not claimed to survive a different bound — the 166 and the 58 are measurements at $24 \times 24$ and nowhere else.

That last observation is the honest summary of how the two games are related: they agree where the arithmetic they run on agrees, which is on dimensions whose only prime factor is two, and diverge everywhere a third or a fifth gets into the factorisation.

Where the search stops, and what is therefore not claimed #

Every number above is a measurement over a bounded range, and the bounds differ between the two games.

Cutcake, computed the way this site has always computed it, stops at $6 \times 6$. The whole table to that size takes 8.3 seconds, and $7 \times 7$ exhausts the game registry after 99 seconds without finishing, which is the ordinary situation rather than a surprise. The comparison tables above reach $8 \times 8$ only because a second implementation was written for them, one that reduces each option before storing it and reaches $40 \times 40$ in 22 milliseconds; the two agree on all 36 cakes both can compute. The slow one is deliberately kept, because the cost of the naive recursion is itself a measured quantity elsewhere on this site.

Maundy Cake reaches $36 \times 36$ in 10.8 seconds, and the growth of the exhaustive search is steep: 144 cakes in 93 milliseconds, 576 in 2.45 seconds, 1,296 in 10.8. The Ω rule is asserted over exactly that range. It is a measured regularity over 1,296 cakes and not a proof, and the counterexample counts quoted against the odd-divisor readings are counts within the same range — a rule can be wrong 946 times out of 1,296 here and nothing about that is a statement concerning a $50 \times 50$ cake.

The largest value found is 22, on the $1 \times 24$ cake. Left’s best cut there is into three $1 \times 8$ strips at 7 each, for 21, and there is no Right cut, so the value is the simplest integer above 21.

Normal play throughout. A player who cannot cut loses, and the entire coldness argument is an argument about who moves last — about which player runs out of cuts first. Under misère play — the player who cannot move wins — a cake worth a comfortable $+7$ is not worth anything of the kind, and none of the integer arithmetic survives the change. Maundy Cake under misère is a different game with the same rules.

What the tables cannot show #

The grids are complete answers to a bounded question and they conceal three things worth naming.

They cannot show the rule they were drawn to test. Cutcake’s zeros form visible blocks: a reader sees squares of doubling size and can guess the binary length from the picture. Maundy Cake’s zeros do not form a shape. They are scattered across the table exactly as a function of $\Omega$ requires, and a scattering is what a completely determined pattern looks like when the function determining it is not geometric. That the zeros are the equal-$\Omega$ cells is asserted on the figure and cannot be read off it.

They cannot show the option trees. The 5×5 Cutcake cell summarises 2,903 positions, and the Maundy cells are the tops of recursions of the same kind. The grid gives no way of seeing which of those positions mattered, or that $2 \times 12$’s value came from a cut into three rather than a cut into two.

They cannot show what is outside them. “No counterexample” is a claim about an absence, and an absence past the edge of the table has no picture at all. The strongest sentence in this essay — that the Ω rule has zero exceptions — is the one with nothing to look at. What makes it checkable rather than merely asserted is that the census keeps every exception it finds and returns them, so a rule that failed once would say so.

Who found it, and when #

Cutcake is Conway’s, and appears in On Numbers and Games (1976) as an early worked example, placed deliberately before the games with fights in them so that a reader can watch the theory produce a complete answer once before being asked to trust it on a hard case.

Maundy Cake is from Winning Ways (Berlekamp, Conway and Guy, 1982), where it sits beside Cutcake with the same moral: a cold partizan game whose values are integers and whose table is organised by a number-theoretic quantity the rules never mention. Its name is the cake of Maundy Thursday, cut into equal portions.

What has travelled since is a one-line summary, and one line is not enough room for this game’s answer. The version that reached this site’s own rung-1 essay — largest odd divisor rather than binary length — is wrong under every reading of it that can be computed, and wrong in a way that is easy to see once the table is drawn and impossible to see from the sentence. Wythoff’s game has the golden ratio in it and is usually restated correctly, because what is being restated is a formula. Maundy Cake’s answer is not a formula, and the compression lost it.

The ladder from here #

This is the second rung of the Cutcake anchor, and the first place its base rung turned out to need correcting.

The rungs above it: the proof that both games are cold, done properly by induction on the options rather than checked over a table, which is what would turn the Ω rule from a regularity over 1,296 cakes into a theorem. Maundy Cake in a hot sum, where an integer-valued component sitting beside a fight becomes a position neither player should ever move in, and where the count of spare moves finally has to be traded against something. The size question on its own — what function of $m$ and $n$ gives the magnitude, given that $\Omega$ gives only the sign, and whether the four values 7, 10, 13 and 16 have a closed form or only a recursion. And the classification of cold partizan games, which nobody has completed: Cutcake is cold, Maundy Cake is cold, Col very nearly is, Domineering on boards this small is not cold at all, and no one can say in advance which side of that line a new game falls on.

The thing established here is smaller than a theorem and more useful than an anecdote. A game one word away from a solved one is not one word away from its solution; the arithmetic can change completely, the received summary can be false, and a table of 1,296 computed values is what tells the difference between the two.