The obvious cut is the wrong one

The short side is not in the lemma closed by naming the next rung and predicting most of it. Maundy Cake’s formula had been proved by rewriting its lemma so that the short side disappeared from the statement, and the closing paragraph asked whether Cutcake — the same game with the equal-pieces clause removed — would go the same way:

The step would have to be cut in half, the analogue of the lemma would be that no other cut beats halving, and the object the short side collapses into would have to be a binary length rather than a multiset.

Two of those three are right. The short side does collapse into a binary length, exactly as predicted, and once it has the lemma is a one-line fact about floors rather than the term-by-term comparison Maundy Cake needed. But halving is not the best cut. It is wrong on a third of all cakes, and the smallest cake it is wrong on has six squares on one side and two on the other, which anybody could have checked by hand in a minute and nobody did — including the page that made the prediction.

The two games, and the one clause between them #

Cutcake is a rectangle of squares. Left cuts along a vertical line, into two pieces; Right cuts along a horizontal one. A player with no cut left to make loses, and every value in the game is a whole number, which is unusual enough to be the reason anybody looked at it.

Maundy Cake is the same rectangle with one clause added: a cut must divide its side into equal pieces. Cutting a side of twelve is then a choice among cutting it into two, three, four, six or twelve, rather than among the eleven places a knife could go — and the whole difference between the two games’ answers comes out of that clause. Cutcake’s cake is worth nought exactly when the two sides have the same binary length, ⌊log₂ m⌋ = ⌊log₂ n⌋. Maundy Cake’s is worth nought exactly when they have the same number of prime factors counted with multiplicity, Ω(m) = Ω(n).

The two rules have nothing in common. Binary length is a statement about where a number sits between consecutive powers of two, and it does not care what the number factorises into: 16 and 31 share a binary length and share no factor above one. Ω is a statement about factorisation and does not care about size: 16 and 81 both have Ω = 4 and sit half an order of magnitude apart. So the same rectangle, cut two slightly different ways, is answered by two statistics that disagree about almost every number — which is the reason the grid above has the cells it has, and why the pair is worth drawing together at all.

That is a satisfying pair of rules and it is not what this page is about. Both were fitted to a grid and then checked on a bigger grid, which is a perfectly respectable thing to do and is not a proof. A rule that has held on forty thousand cases is a rule that has held on forty thousand cases; the forty thousand and first is a separate event, and the difference between believing it will hold and knowing it will is the difference this ladder has spent two rungs on. Maundy Cake’s stopped being fitted; the question here is Cutcake’s.

The step, with the maximum taken honestly #

Maundy Cake’s step is a clean recursion because its cut is forced:

$$V(m, n) = 1 + P_1 \cdot V(m, n / P_1)$$

Cut the long side at its largest prime factor, and the mover is handed P₁ copies of a smaller cake, plus the move itself, which is worth one. Cutcake has no forced cut, so the step cannot name one. It has to say what the value is in terms of all of them:

$$V(m, n) = 1 + \max_{1 \le i < n} \left[ V(m, i) + V(m, n - i) \right]$$

— the value is one more than Left’s best cut, where the maximum runs over every one of the n − 1 places a knife could go.

That identity holds on all 33,065 cakes to 300 × 300 whose long side is strictly longer in binary length, with no exceptions, and the maximum in it is taken honestly — every cut is evaluated, not just a nominated one. That distinction is the entire value of the row. A step checked at the cut expected to win is not a check at all; it is the assertion restated, and it would pass on a game where some quite different cut was better. Evaluating all n − 1 of them is what makes the row capable of failing.

It is checked only on the branch where one side is strictly longer, and the omission is deliberate rather than a gap. When the two sides have the same binary length the cake is worth nought, Left has nothing worth one, and the identity is false there because it ought to be — Left’s best cut is worth −1 and adding one to it gives nought, which is right by accident on some cakes and wrong on others. The level case is where the induction bottoms out, and it bottoms out on a different argument: neither player has a cut that leaves them ahead, which is a sentence about the rules rather than a sweep.

The first row of that table is the only place the game itself appears. Everything else on this page is computed from an expression — ⌊n / 2^⌊log₂ m⌋⌋ − 1 — and an expression is not a game. So the expression is checked against the actual construction, options built and reduced, on every cake the construction can reach. It reaches six by six, which is thirty-six cakes, and thirty-six is not many; it is, however, all there is, because building a Cutcake position as a game tree is exponential in both sides and this site says so in its own price of a value. Those thirty-six cakes are the whole of the evidence that the fast route is the game’s route, and every number below them rests on it.

Which cut attains it #

With the step stated, the argument is where Maundy Cake’s was: everything now depends on which cut attains the maximum, because a cut with a name turns a maximum into a recursion and a recursion into a formula.

The ladder predicted halving, and the reasoning behind that prediction is worth stating because it is good reasoning. Maundy Cake’s best cut is the largest prime, which is the cut that makes the fewest, largest pieces — the most balanced cut the divisor clause allows. Remove the clause and the most balanced cut available is a cut down the middle. It is the obvious analogue and it is what a reader would try first.

It is wrong on 10,920 of the 33,065 cakes, a third of them, and what is right is a different cut entirely. Write w = 2^⌊log₂ m⌋ for the widest power of two the short side covers — call it the cake’s slab. Then cutting off exactly one slab from the long side is a best cut, on every cake here, without exception.

The smallest disagreement is the 2 × 6 cake. Cut it in half and it is two 2 × 3 pieces, each worth nought, so the halving move is worth nought. Cut it at two, or at four, and it is a 2 × 2 worth nought beside a 2 × 4 worth one, so the slab move is worth one. The cake is worth two, which is one more than the best cut, and halving misses it.

It is worth being precise about what “best” means here, because the slab is not uniquely best and the lemma does not claim it is. On the 2 × 12 cake there are five cuts tied at the top — at 2, 4, 6, 8 and 10 — and on the 3 × 9 cake there are six, including cuts at odd places. The rung that first chose among tied cuts is where this anchor first had to choose among tied cuts, and it chose by a rule that reads both sides rather than by picking the largest. What the lemma claims is that the slab is always among the best, which is exactly what a step needs: an induction wants one cut it can always name, not the only cut worth making. Maundy Cake’s lemma has the same shape and the rung below it spends a figure on the ties for the same reason.

Once the slab is the cut, the recursion unrolls without any effort at all. Cutting off one slab leaves a piece worth nought and a cake one slab shorter, so each cut is worth exactly one and there are ⌊n/w⌋ − 1 of them before the cake goes level. That count is the closed form. Maundy Cake’s unrolling produces running products of primes and needs a page to write down; Cutcake’s produces a count of slabs and needs a sentence — and the size of a cake, which is the one-row case with every term kept, is that same walk written out for a reader rather than compressed.

And the criterion for when halving does happen to work is exact rather than approximate: it is best precisely when the two halves’ remainders modulo the slab fit inside one slab. That is checked as an equivalence in both directions on all 33,065 cakes rather than as a rule of thumb, which matters, because a criterion that were merely usually right would be indistinguishable from the guess it replaced.

The lemma, once the short side is gone #

Now the move that made the Maundy proof work. The lemma there — no divisor beats the largest prime — looks like a statement about a cake, with a short side in it, and a statement about cakes has to be swept over pairs. Rewritten, the short side turns out never to appear: it becomes an inequality between running-product sums over a multiset of primes and a term count, and one instance of it settles every cake with that long side and any short side whatsoever.

Do the same here. Left’s cut at i leaves pieces worth ⌊i/w⌋ − 1 and ⌊(n−i)/w⌋ − 1. The claim that no cut beats the slab is the claim that the two pieces can never hold more whole slabs than the cake they came from:

$$\left\lfloor \frac{i}{w} \right\rfloor + \left\lfloor \frac{n-i}{w} \right\rfloor \;\le\; \left\lfloor \frac{n}{w} \right\rfloor$$

The short side is gone. What is left is a statement about two integers, a width and a slab, and it is superadditivity of the floor function — the oldest fact about floors there is, one line, and the same line whatever m was.

It is worth pausing on how much shorter that is than what it replaces. Maundy Cake’s inequality compares two sums of running products of primes, term by term, and the comparison has to be set up so that the terms of one dominate the terms of the other in the right order — which is a real argument, and the rung below spends a figure on the term-by-term table because the pairing is where the work is. Cutcake’s has no terms to pair. Both sides are single floors, and the fact that a sum of floors never exceeds the floor of the sum is true of every real number, not of anything about cakes.

The sweep is there anyway, on sixty-eight million cuts across nine slab widths, for the reason this site runs on: a lemma with a proof and no test is a lemma nobody has read carefully enough. It reports one more thing, which is not decoration. The inequality is tight on 62.1% of those cuts — the two pieces do hold exactly as many slabs as the cake — and tightness is what makes the step an equality rather than a bound. A lemma that were true and never attained would prove the value is smaller than the closed form says, which is a different result and a wrong one.

What one instance buys #

The reason to care whether the short side is in a statement is not elegance. It is that a statement with the short side in it needs one instance per cake, and a statement without it needs one instance per class of cakes.

Over every cake to 300 × 300 whose second side is the longer, the value never once distinguishes two short sides that share a binary length — 56,935 cakes, no violations. That collapse is the licence to state the lemma about (n, w) rather than about (m, n), and it is checked rather than assumed, because if it failed anywhere the instance counting below it would be meaningless.

The counting: 33,065 cakes with a strictly longer side need 1,898 distinct instances, seventeen cakes an instance, and the widest single instance settles a hundred and twenty-eight cakes at once — every short side between 128 and 255, all of which have the same binary length and therefore the same lemma. On the same grid, a statement written with the short side in it would need one instance for each of the 33,065.

The classes are also the right classes, which is not automatic. A statement can be true of every cake and still be stated at the wrong grain — one could group cakes by their short side’s parity, prove something true of each group, and have gained nothing, because the groups do not close under the recursion. Binary-length classes do close under it: the step takes a cake with short side m to another cake with short side m, so the whole induction stays inside one class from beginning to end, and a lemma proved for the class is a lemma available at every step of it. That is what makes the grouping an argument rather than a bookkeeping convenience.

That ratio is the whole difference between a sweep and an argument. Seventeen to one is not a large factor and it is not supposed to be: what matters is that the ratio grows without bound, because the number of short sides in a binary-length class doubles with the class. A sweep over pairs never finishes at any size. A sweep over classes finishes at every size, and the reason is not that the second is faster but that the second is a different statement.

Where the two arguments part #

Put both proofs side by side and they take the same five steps: the value’s closed form, the step, the lemma naming a best cut, the lemma restated without the short side, and the collapse that makes the restatement legal.

The furniture differs in one place and it propagates. Maundy Cake’s short side collapses into Ω(m), a count over a multiset of primes, so its lemma is an inequality between two running-product sums and closing it takes a term-by-term comparison — real work, and the reason that rung took a whole page. Cutcake’s collapses into ⌊log₂ m⌋, a single integer, so its lemma is an inequality between floors and closing it takes a line. Removing a clause from the rules made the game wilder — every cut is legal instead of only the divisor cuts — and made the proof shorter, which is not the direction anybody would predict.

The one line where they genuinely part company is the guess. Maundy Cake’s most balanced cut is the right cut; Cutcake’s is not. That is the price of letting the knife go anywhere: with only divisor cuts available, balance and arithmetic point the same way, because a cut into P₁ equal pieces is both the most balanced cut and the one that peels a whole prime off the factorisation. With every cut available they come apart, and the cut that matters turns out to be the arithmetic one — land on a slab boundary — rather than the balanced one. Halving is best only by accident, when the middle happens to fall where a slab boundary already is.

What the ladder now says #

Seven rungs, and the last two are theorems where the first five were rules read off grids. Cutcake’s rule and Maundy Cake’s are both proved, by arguments with the same shape, and the shape is find the variable the statement does not depend on and take it out.

That is worth stating on its own because it is portable and this site keeps meeting it. A period is a proof is the same move in a different disguise: a sequence’s behaviour cannot depend on how far along it the reading started, so a window long enough to cover a period settles the whole sequence. The short side only says how many was the first place this anchor noticed that a whole side of a cake enters the answer through one number. And what solved means is the list this ladder has now walked most of: a value for one position, a rule fitted to a grid, a formula checked on tens of thousands, a theorem.

What is left here is smaller than it looks. Both proofs assume the game’s values are integers, which is checked and not derived — thirty-six cakes for Cutcake and forty thousand for Maundy Cake, both of them measurements. An argument that produced integrality rather than confirming it would close the last gap in both games at once, and it would have to come from the simplicity rule rather than from either cake, because the two games have nothing else in common. The strip where every number is a whole one is the nearest thing on this site to such an argument, and it is about a different family of positions entirely.

And the prediction that failed is the useful part of the page. It was not a careless guess: it was the right analogy, reasoned from the game the argument came from, and it fails because the analogy carries balance across and the games care about arithmetic. Checking it took one cake with twelve squares in it. That is the whole moral, and it is not about cakes.