Cutcake, where every value is a whole number

A rectangular cake, scored into unit squares. Left cuts along a vertical scoring line, all the way through, separating the cake into two pieces. Right cuts along a horizontal one. Whoever cannot cut loses.

Both players are cutting the same cake with the same scissors, and the only asymmetry is the direction. That makes it partizan — the two players see different games on the same object — which is what Domineering is famous for and what usually produces values like $\{1 \mid 0\}$ and $\uparrow$ and things with stars in them.

Cutcake produces none of those. Every value is a plain whole number.

Why nothing is ever at stake #

The values are integers because Cutcake is cold: neither player ever gains by cutting.

A cut does two things. It gives the cutter one move’s worth of progress, and it hands the opponent a position with more pieces in it — and more pieces means more scoring lines of the other direction, which is to say more moves for the opponent as well.

More precisely, cutting an $m \times n$ cake vertically into $m \times i$ and $m \times (n-i)$ leaves Right with exactly as many horizontal cuts available as before — $m-1$ in each piece, where there were $m-1$ in the whole. Left has gained a move; Right has lost nothing.

So the cut costs Left nothing and gains Left nothing that waiting would not also have gained. Both players are in the same position, and neither has any reason to hurry. A game in which nobody wants to move is a game in which nothing is at stake, and a game with nothing at stake is worth a number.

That it is a whole number takes one more step, and it is the reason the pattern is what it is.

The value is a count of spare moves #

Read the table. The $1 \times 4$ cake is worth $3$; the $4 \times 1$ cake is worth $-3$. The $1 \times n$ cake is worth $n-1$, which is exactly the number of vertical cuts in it — all of them Left’s, none of them Right’s.

That is the general shape. A Cutcake value is the number of moves one player has in hand after the other has run out, and it is an integer because moves are counted in whole numbers. The game reduces, in the end, to arithmetic on move counts.

$$\text{value} \;=\; (\text{Left's total cuts}) - (\text{Right's total cuts}), \text{ eventually.}$$

The word “eventually” is doing real work and is where the game stops being trivial. The counts are not simply $n-1$ and $m-1$: cutting multiplies the pieces, and each piece then has its own count, so the totals depend on how the cake is divided rather than only on its dimensions.

The blocks #

The zeros in the table are not scattered. They form blocks: $1\times1$; then the whole $2$-to-$3$ square; then the whole $4$-to-$7$ square, of which the table shows a corner.

The rule is that an $m \times n$ cake is worth nothing exactly when

$$\lfloor \log_2 m \rfloor = \lfloor \log_2 n \rfloor,$$

that is, when $m$ and $n$ have the same number of binary digits. A $5 \times 7$ cake is balanced; a $5 \times 8$ cake is not, because $8$ has one digit more.

That is a strange thing to fall out of a cake. The rules mention no powers of two, no logarithms and no halving, and the game is played by cutting a rectangle in whatever proportion a player likes.

The mechanism, briefly: a player cutting a cake in half doubles the number of pieces available to them at half the size, so the game is really about how many times each dimension can be halved before it reaches one — which is the number of binary digits. A player with more halvings available has spare moves, and the count of spare moves is the value.

It is worth seeing why the natural guess is wrong. A reader looking at the first block might expect balance when $m = n$, and the table refuses: $2\times3$ is balanced and $3\times4$ is not, although both differ by one. The quantity that matters is not the difference between the dimensions, and not their ratio either — $4\times7$ is balanced with a ratio close to two, while $3\times4$ is not, with a ratio of a third of that.

What separates them is a threshold, crossed at $2$, $4$, $8$ and so on. A dimension of $4$ and a dimension of $7$ afford the same number of halvings; a dimension of $3$ and a dimension of $4$ do not. That is why the shaded regions are squares of doubling size rather than a band along the diagonal, and it is the shape a reader should look for whenever a game’s answer turns out to be about counting operations rather than about sizes.

A five-by-five table shows only the corner of the third block, which is the one large enough to have an interior. Running the same computation out to six squares on a side shows nine of that block’s cells rather than four, and with them the thing the smaller table cannot make visible: that inside a block the value is flat, and that the flatness extends sideways as well as diagonally.

That row is the mechanism stated in numbers. Widening the cake from two columns to three changes nothing at all, and widening it from three to four changes the answer by two whole moves — because the second widening crosses a threshold and the first does not. A rule about sizes could not produce a table with flat stretches and cliffs in it; a rule about how many times a number can be halved produces nothing else.

Domineering is the contrast worth holding in mind, since it is played on the same shape of board with pieces instead of cuts. At these sizes it produces fractions, stars and fights, because a placed domino takes squares the opponent wanted. A Cutcake cut takes nothing from anybody, and that difference is the whole of why one table is integers and the other is not.

Following one cake through #

The recursion is short enough to run by hand on a small cake, and doing so makes the block pattern less mysterious.

The $1 \times 1$ cake has no scoring lines at all. Neither player can cut, so whoever must move loses, and the value is $0$.

The $1 \times 2$ cake has one vertical line and no horizontal one. Left can cut it into two $1\times1$ cakes, each worth $0$, so Left’s option is $0 + 0 = 0$. Right has nothing. The value is $\{0 \mid\ \} = 1$: Left has one spare move.

The $1 \times 3$ cake. Left’s cuts give $1\times1$ plus $1\times2$, worth $0 + 1 = 1$, or $1\times2$ plus $1\times1$, the same thing. Right has nothing. So the value is $\{1 \mid\ \} = 2$.

The $2 \times 2$ cake. Left cuts it into two $2\times1$ cakes, each worth $-1$ by the mirror of the second case, so Left’s option is $-2$. Right cuts it into two $1\times2$ cakes, worth $+1$ each, so Right’s option is $+2$. The value is $\{-2 \mid 2\}$, and Left’s option is below Right’s — which is the signature of a cold position. The simplicity rule applies and gives the simplest number strictly between $-2$ and $2$, which is $0$.

That last case is the whole argument in miniature. Left’s best move leaves Left worse off by two and Right’s leaves Right worse off by two, so neither wants to go first, and the position settles at the number in the middle.

$$\{-2 \mid 2\} = 0, \qquad \{1 \mid \ \} = 2, \qquad \{-2 \mid 2\} \neq \pm 2.$$

The contrast with a switch is exactly the direction of the inequality. $\{2 \mid -2\}$ — Left’s option above Right’s — is a fight worth nothing on average and everything to whoever moves. $\{-2 \mid 2\}$ is worth nothing, full stop. The same two numbers, in the opposite order, and one is the most urgent thing on a board while the other is the least.

A switch has width: drawn as a bar between its two options it stands up off the axis, and both players want to be the one who takes it. Cutcake has the two options the other way round in every position it can reach, so there is never a bar to take, and every value collapses to a point in the middle of a gap neither player wants to enter. That is why nothing in this essay’s table is a fight, and why the argument for the whole family reduces to an argument about one inequality’s direction.

What the solver computed, and how #

The table is built by the game recursion, and nothing in the generator knows about integers, logarithms or blocks.

An $m \times n$ cake is a game whose Left options are the sums $\text{cake}(m,i) + \text{cake}(m,n-i)$ for each $i$ from $1$ to $n-1$, and whose Right options are the corresponding horizontal splits. Each option is a genuine disjunctive sum — two independent cakes, played at once — and the sum is formed by add rather than by any bookkeeping on numbers.

The value comes back from canonical and name, which know nothing about Cutcake. The generator then refuses to draw any cake whose name is not a plain integer: no fraction, no star, no braces. A single value of $\tfrac12$ or $\{1\mid0\}$ anywhere in the table would fail the build.

The site’s gate makes the block pattern a claim as well. It checks all twenty-five cakes up to $5 \times 5$ and requires two things: that every value be an integer, and that a value be zero exactly when the two dimensions have the same number of binary digits. The second requirement is the one that can fail interestingly — a bug producing all zeros would pass the first and fail the second immediately.

One practical note, because it changed how the figure is written. Deciding whether a value is a number by walking the game tree is prohibitively expensive on a large cake — the $5 \times 5$ recursion takes the better part of a minute that way. Deciding it from the name, which has already been computed, is instant and is exactly as strong a check: a value whose name reads as an integer is that integer.

Where the model stops #

The table stops at six. A $6 \times 6$ cake takes several seconds and a $7 \times 7$ exhausts the memory the interning table can hold, so the largest grid on this page is the largest one there is. The block pattern is stated for all $m$ and $n$; the gate checks it up to five and the figures draw it up to six. That a game this simple runs out of room this quickly is the ordinary situation rather than a surprise.

Coldness is the whole story and it is a strong condition. Almost no game is cold. Cutcake is, Col nearly is, and everything else on this site has fights somewhere in it. Taking Cutcake as representative of partizan games would be a serious mistake — it is representative of the corner of them where the theory is easiest.

“No decisions” is not quite true. Unlike Brussels Sprouts, where the outcome is fixed before play, Cutcake does have decisions: a player who cuts badly can lose a won position. What it lacks is tension — nothing is ever gained by moving first, so the decisions are about counting rather than about timing.

Normal play. The whole coldness argument is about who runs out of moves, which is a statement about who moves last.

What the table cannot show #

The grid of values is a complete answer to a bounded question and it hides three things worth naming.

It hides the option trees. The $5 \times 5$ entry is the top of a recursion over every way of splitting a cake into two, each of those into two, and so on. The number $0$ in that cell is the summary of several thousand positions, and the table gives no way of seeing which of them mattered.

It hides the play. A value of $2$ says Left is two spare moves ahead. It does not say where to cut, and — unlike a fight, where the move follows from the value — a Cutcake player still has to choose. Cutting a $2 \times 5$ cake into $2\times1$ and $2\times4$ is not the same as cutting it into $2\times2$ and $2\times3$, and the value of the position afterwards differs.

It hides why the blocks are square. The pattern is visible and the table gives no mechanism for it. A reader looking at the shaded blocks can see them; nothing in the picture explains why the boundaries fall at powers of two, and the explanation is not something a grid of numbers can carry.

That last one is the general case of the site’s caution about pictures. A figure can show that a pattern holds over the range drawn. It cannot show why, and it cannot show what happens past the edge — which for this table is every cake larger than five squares on a side.

Why every value being a number is the strong statement #

Every position is worth a whole number sounds like a small claim about a small game, and it is one of the strongest statements this site makes about any ruleset. It is worth unpacking what it rules out.

A position worth a number is a position where every move loses ground for the player making it, all the way down. So a claim that every position of a game is a number is a claim about the entire game tree: no position anywhere in it has a move worth making, no position is confused with anything, and there is no fight at any depth.

That is far more than saying the game is easy. A game can be easy and hot — Nim is settled by three exclusive-ors and every non-empty Nim position is confused with nought. It can be hard and cold. Easiness is about computing the answer and coldness is about what the answer is, and Cutcake happens to be both, for one reason: a horizontal cut and a vertical cut never affect each other’s availability, so the two players’ moves are two disjoint supplies and the value is a difference of counts.

It also says what a player is actually doing. If every move loses ground, neither player wants to move, and the whole game is about being the one who does not have to. The position is a standoff from the first move to the last — which is what numbers avoid numbers says of a number sitting on a board with something else, applied here to a board with nothing else on it.

Which is why the family is worth a page despite having no fights in it. It is the clean specimen of the condition, and every other game on this site is what happens when the two players’ supplies start to interfere.

What a game with no fights is for #

A game that produces only integers sounds like a game with nothing to say, and the opposite is true: it is the cleanest place in the subject to see what a value is.

Everywhere else, a value is a compromise between two players’ preferences and its interpretation is contested — a fraction means something about a position that neither player controls, a star means something about parity, an up means something about a margin too small to name. In Cutcake a value means one thing, unambiguously: this many spare moves. There are no infinitesimals hiding in it and no star to account for.

That makes it the right example for two arguments that are harder to make elsewhere. It shows that partizan does not imply hot, which is a distinction people conflate constantly. And it shows the additivity theorem doing its work in a setting where the arithmetic can be followed by hand — a cut turns one cake into two, the values add, and the reader can check the addition.

The blocks are the third thing, and they are the surprise. A game about cutting rectangles with no numbers in its rules produces a table organised by binary digits, and the reason is that halving is the operation both players are competing to perform more often.

Who found it, and when #

Cutcake is Conway’s, and it appears in On Numbers and Games as an early example — deliberately placed before the games with fights in them, because its values can be worked out completely and the reader can see the theory produce a full answer once before being asked to trust it on harder cases.

The generalisation, Maundy Cake, appeared in Winning Ways: the same rules except that a cut must divide the cake into equal pieces. Its values are also integers, and they are decided by a different arithmetic function of the sides — not the binary length, and, as the census of every cake to 36×36 shows, not the largest odd divisor either, which is the rule this essay carried until that census was run.

One clause, changed, and the two answers can be set in the same grid to see how far apart it puts them.

That is the useful thing about the pair. Both games hand back whole numbers and neither ever hands back a fraction, so the kind of answer survives the change of rule intact; what does not survive is the arithmetic that decides it. Cutcake counts halvings and Maundy Cake counts prime factors, and the two counts agree often enough to look like the same rule on a small table and part company on half of one this size.

The pattern of a combinatorial game producing an unexpected number-theoretic table is not rare. It shows up in Wythoff’s game with the golden ratio, in the periodicity of octal games, and here with binary digits, and in each case the mechanism turns out to be a halving or a partition that the rules perform without mentioning.

The ladder from here #

cutcake opens here with the game whose every value is a whole number and whose rule is about binary length.

Maundy Cake is the same game with one clause changed — the cut must be into equal pieces — and the whole answer changes with it: binary length is replaced by $\Omega$, the count of prime factors with multiplicity, and a game about halving becomes a game about factorising.

The size of a cake then asks what a Maundy Cake is worth rather than who wins it, and finds the greedy rule — cut at the largest prime — right four times in five, with 104 exceptions it can describe only as both sides composite.

The two rungs above turn that residue into a complete answer. The rule for which prime to cut at finds all 104 taking the opposite cut, at the smallest prime, with no middle divisor ever needed anywhere in a sixty by sixty grid — and which of the two extremes wins decided by $\Omega$ alone: cut small when $\Omega(m)+1 \ge \Omega(n)$, large otherwise, exact on all 3,540 cakes. And the short side only says how many closes the size question: with the cut settled the recursion unrolls into the running products of the long side’s prime factors, largest first, while the short side contributes nothing but a count of how many of them to take. Sixty-two different short sides give one value.

So a family that begins here as a game whose values are integers ends four rungs up as a game whose values are a sequence and a length, and the second variable turns out never to have been a variable at all.