The square that cannot be halved

The strip where every number is a whole one measured something and could not say why. Delete the hop from Toads and Frogs — no piece jumps over another, everything else the same — and among the seven thousand seven hundred and forty-six strips to eight squares that are worth a number, every single one is worth a whole number. Not one half, not one quarter, not one up.

That page closed by naming the proof it did not have:

the proof would go by showing that a hopless position with no contested odd gap is worth a count of free moves — which is the sort of statement that either falls out in three lines or needs a careful invariant, and either way is a rung rather than a remark.

It falls out in about five lines, and then it needs a careful invariant for the case it does not cover. Both halves are here.

The distinction matters more than it usually does, because the condition in that sentence is doing two different jobs. No contested odd gap is a sufficient condition for the value to be a number, and the five lines establish it. Whether it is also necessary is a separate question with a separate answer, and the answer is no — which is the part the rung below had no way to guess, since a condition that holds on seven thousand seven hundred strips and never fails looks necessary from the inside.

Cutting the strip up #

Nothing in this game turns round and nothing passes anything. A toad moves right for ever; a frog moves left for ever; with the hop gone, neither can get past the other. So the order of the pieces along the strip is fixed from the first move to the last, and that single sentence does most of the work.

It gives two kinds of permanent wall.

A toad immediately left of a frog is one. The toad’s square ahead is occupied and so is the frog’s, and nothing behind either of them can change that, because nothing behind can get past. That is the wall the previous rung checked the addition across.

A frog anywhere left of a toad, with only empty squares between, is the other and is the more useful one. The frog moves away to the left and the toad away to the right, so neither will ever enter the gap, neither will ever reach the other, and the two sides of it never interact again. The strip falls into pieces that add.

Cut at every wall of the second kind and what is left of each piece has all its frogs to the right of all its toads. So a component is a block of toads, one gap, and a block of frogs — and that is the shape the whole argument needs. Everything below is about one component, and the strip is their sum.

Three kinds of empty square, and then a fourth #

Inside a component there are three places an empty square can be, and the difference between them is the difference between an integer and a fight.

A gap inside the block of toads belongs to Left. No frog can reach it — the frogs are all on the far side of the contested gap and none of them will ever cross it. So Left will eventually make every move that gap contains, whatever Right does, and Right cannot stop, delay or profit from any of them. Closing the gap between the ith toad and the next costs i moves once the toads behind have followed up, so a block of toads is worth Σ i·gᵢ free moves to Left. The frogs’ blocks are the mirror image.

The weighting is worth a moment, because the obvious count is wrong. A gap of one square between the second and third toads is not one move: the second toad moves into it, which opens a square behind, which the first toad moves into, so a single empty square two toads deep is worth two moves. That is the i in the sum, and getting it wrong would give the right answer on every strip with one toad and the wrong answer on most others — which is exactly the kind of error the sweep below exists to catch rather than the kind an argument catches.

The contested gap is split down the middle. Here both players can move in and neither can be stopped. Of G empty squares each takes G/2, and — this is the part worth stating carefully — each takes them with the whole block behind them, so the a toads gain a·G/2 moves between them and the b frogs gain b·G/2. The net contribution is (a − b)·G/2.

The even split is not an assumption about good play; it is forced. Neither player can decline to take their half — declining means passing, and there is no pass — and neither can take more, because the moment the two blocks meet the gap is gone. So the number of squares each side ends up with is determined by the rules and not by the players, which is the property that makes this a count rather than an outcome. It is also the property the hop destroys.

Add the three up and the component is worth an integer. Every square is either one player’s alone or divided evenly; there is nothing left over and nothing to fight about; and the value is a count of moves rather than a position in a fight. That is what an integer as a game value means here and it is the whole of what these positions are: a supply of moves for one side, with the other side having nothing to say about it.

Unless G is odd. Then it cannot be split evenly. One square is left over, whoever moves takes it, and taking it is worth having — so the component is not a number at all. It is a switch, and the two options differ by a + b − 2, which is the number of pieces in the component less two.

Over every strip to nine squares — twenty-two thousand one hundred and eighty-six of them have no contested odd gap in any component — the value is a number and the number is exactly that count. Not one exception.

Both halves of that are checked separately, and they are different claims. Is a number would be satisfied by a value of one half, which would refute the whole page while leaving the sweep green if the sweep only asked the weaker question. Is this particular integer is the statement with content, and it is the one that would break first if any of the three counts above were weighted wrongly.

That is the rung below’s statement, and it is now proved rather than measured. It also explains the observation it came from: the values are whole numbers because every empty square is a whole move that somebody gets, and the only thing that could produce a fraction is a square that has to be shared unevenly.

One odd gap is fatal #

The obvious next thought is that the theorem’s condition is also necessary — that a contested odd gap means the position is not a number. Half of that is right.

Six thousand nine hundred and eighty-five strips have exactly one component with an odd contested gap, and not one of them is a number. That is not a measurement so much as a restatement: a switch in a disjunctive sum leaves the sum a switch, because the other components are numbers and a number plus a switch is a switch.

Three odd gaps behave the same way and there is exactly one such strip in this range, which is worth noting precisely because one case is not evidence. It is not a number, and the reason three should behave like one is that two of them can cancel and the third is then alone — but a single instance does not establish that and this page does not claim it does.

The scarcity is structural rather than accidental. Each component with an odd contested gap needs at least a toad, a gap and a frog, and each pair of components needs a wall between them, which needs a frog to the left of a toad. Three of them is nine squares at the very least and the ninth square is the whole budget, so one strip is all there is room for. Ten squares would hold several and would be the place to look.

Two is where it gets interesting.

Two can cancel #

Three hundred and fifty-one strips to nine squares have exactly two components with odd contested gaps, and a hundred and forty-three of them are numbers.

The smallest is T.FT.F, six squares, worth nought. It is two copies of T.F, each of which is a component with one toad, one frog and a gap of one — each worth star. Two stars add to nought, and nought is a number.

Star is the degenerate case and it is worth seeing why. A component with an odd gap is a switch whose two options differ by its piece count less two; with one toad facing one frog that difference is nought, the two options coincide, and a switch whose options coincide is not a switch — it is that number with a star on it. So the smallest exception to the theorem’s converse is also the one where the switch machinery below is invisible, which is exactly why the general rule was not obvious from it.

The general case is not about stars and it is not about gaps. A component with an odd contested gap is a switch whose two options differ by its piece count less two — the swing is a count of pieces, and the gap’s own length has dropped out of it entirely, appearing only in the mean. Two switches add to a number exactly when their swings agree, because then whoever moves first takes the good half of one switch and the opponent takes the good half of the other, and the two halves cancel.

So: two odd contested gaps cancel exactly when their components hold the same number of pieces. Three hundred and fifty-one strips, a hundred and forty-three on one side of the criterion and two hundred and eight on the other, and the criterion agrees with the value on every one.

The thing to notice is that the criterion has nothing to do with the gaps. T.FT.F cancels and so does TT.FTT.F, whose gaps are also both one; but TT.FT.FF cancels too, and its components hold three pieces each while looking nothing alike. What matters is how many pieces are in each component, which is a quantity the gap length does not mention.

This is the same shape of result as a fraction does not reach on the neighbouring anchor, where a rule stated on the shape of a strip turned out to be a rule about a number the shape happens to determine. Here the tempting statement is two odd gaps of the same length cancel, which is true of the smallest examples and false in general; the true statement counts pieces, and the gap lengths that made the first examples look like a pattern are not in it at all.

What the hop was doing #

Put the two halves together and the shape of the answer is clear enough to say what the hop was for.

Without the hop, a piece’s route is fixed and the only question about any empty square is who gets to it. Every square has an owner or a fair split, so every value is a count, and the one place counting fails is an odd number that will not divide by two. That is why the values are integers, and it is why the exceptions are switches rather than fractions: an unsplittable square is a whole move that one player or the other will take, which is a fight over one move and not a fraction of one.

Restore the hop and none of that survives. A toad can leave the square in front of it and reappear beyond a frog, so the order of the pieces is no longer fixed, walls are no longer permanent, and a gap is no longer owned by anybody. The strip nobody has a formula for is what that costs: the same game with the clause restored has fractions, has ups, and has had no formula for decades.

The comparison sharpens a claim the earlier rung could only gesture at. It is not that the hop adds complexity. It is that the hop destroys the one structural fact this whole argument rests on — that a piece’s neighbours are its neighbours for ever — and everything above follows from that fact and nothing else.

What is proved and what is checked #

Worth separating, because the two halves of this page have different standing.

The theorem is proved. A hopless position with no contested odd gap is worth its free-move count, and the argument is the five lines above: the walls are permanent because pieces do not pass, the components add, within a component each empty square is owned or split evenly, and the total is a signed count. The sweep over twenty-two thousand strips is a check on the argument rather than the reason to believe it.

The cancellation criterion is measured. That two switches with equal swing add to a number is a fact about sums of switches and is not in doubt; that the swing of one of these components is its piece count less two follows from the corridor formula the rung below checked. What is measured rather than argued is that these are the only two cases — that no strip in range is a number for a third reason. Three hundred and fifty-one strips is not many, and a fourth kind of cancellation would show up first in a longer strip.

And the sweep is bounded at nine squares because the number of strips is 3ⁿ and the value of each is a game tree. Nine squares is nineteen thousand six hundred and eighty-three strips; ten is three times that, and the trees are bigger too. What a search can settle applies here in its usual form: the bound is stated because a sweep that stops somewhere has said nothing about what lies past it, and this one stops one square short of where a third odd gap becomes common.

Where the ladder goes next #

toads-and-frogs has five rungs: the game, the strip nobody has a formula for, the same strip without the jump, what its values turn out to be, and now why.

The rung above is the switches themselves. This page proves what the numbers are and treats everything else as not a number, which is a large category holding six thousand nine hundred and eighty-five strips in nine squares alone. The corridor formula gives the value of a single odd-gap component in closed form, and the components add, so a closed form for the whole hopless game is now within reach in a way it was not: the value of any strip is a sum of integers and switches whose forms are all known. What is missing is the reduction — a sum of switches has a canonical form and the sum of several is not simply the list of them — and doing that would turn “every number is a whole one” into “here is every value”, which is the statement the anchor has been circling since the hop was deleted.

Two neighbours are worth the trip. Nothing worth fighting over is the other game on this site whose values are all cold, where the reading also fails and fails differently. And the strip where every number is a whole one is the census this page explains, worth rereading now that the fourth column has a reason behind it rather than a count.