The strip where every number is a whole one

The same strip without the jump deleted one clause of the rules — the hop over an opposing piece — and found the values changing on most strips. It closed with a guess:

If the hop is what produces the fractions and the ups, then the jumpless game ought to have a formula: an integer read off the gaps.

Half of that is exactly right and the other half is exactly wrong, and the two halves are worth separating carefully.

Every number is a whole number #

Nine thousand eight hundred and one strips, from four squares to eight. Seven thousand seven hundred and forty-six of them are numbers, and every single one is an integer.

Not one half. Not one quarter. Not one up.

Toads and Frogs is full of fractions — a strip of six produces forty-six of them — and deleting the hop removes every one. The same strips, the same pieces, the same board, one clause of the rule gone, and a whole class of values gone with it.

Why the hop is where the fractions come from #

The mechanism is visible once the two rules are set beside each other.

Without the hop a piece may only shuffle into an adjacent empty square. So the pieces keep their order for ever — a toad can never get past a frog and a frog can never get past a toad — and once a toad sits immediately left of a frog, both are stuck permanently. Play consists entirely of consuming empty squares, and an empty square is one move for whoever reaches it.

That is a game of counting, and counting produces integers. It is the same reason Cutcake’s every value is a whole number: when a move can only spend a resource that nobody else can reach, the position is worth the count of what each player has left, and there is nothing for a denominator to record.

With the hop a piece can pass another, which does two things. It creates positions where a player’s move unblocks the opponent, and it makes the number of moves remaining depend on the order they are made in. A half arises exactly when a player has a move that gains something and gives something back — the ambiguity that a dyadic denominator records — and the hop is what supplies it.

And it is not all numbers #

Of the 6,561 strips of eight squares, 5,071 are numbers, 1,460 are switches with whole-number walls, and thirty are switches with a star attached — values like $\{1\ast \mid \ast\}$ and $\{2\ast \mid \ast\}$.

So there is no function of the gaps that gives the value, because a switch is not a count of anything. The guess assumed that removing the source of fractions would leave a game whose value is a number, and removing it leaves a game whose values are integers or fights.

The switches are where the contest is, and they are common: 1,460 of 6,561 at eight squares, which is 22 per cent, against six of eighty-one at four squares, which is seven. Contests get commoner as strips get longer, because a longer strip has room for more of them. A strip like $\texttt{TT.F}$ is worth $\{1 \mid 0\}$: Left moving first ends up a move ahead, Right moving first ends up level, and the position is worth taking. The empty square between the toads and the frog is contested — either side can move into it — and whoever does is one move better off.

The corridor has a closed form #

There is one shape of strip that does have a formula, and it is worth stating because the formula is short and the checking is exhaustive.

A corridor is $a$ toads, then $k$ empty squares, then $b$ frogs, and nothing else. Write $m = \lfloor k/2 \rfloor$. Then

$$k \text{ even:} \quad m(a-b)$$

$$k \text{ odd:} \quad \{\, m(a-b) + (a-1) \;\mid\; m(a-b) - (b-1) \,\}$$

An even gap gives a whole number and an odd gap gives a fight. That is a parity argument in the plainest possible form: with an even number of contested squares the two sides take half each and the count comes out level; with an odd number somebody gets the extra square, and which of them does is worth exactly one move.

The form was checked against the solver on every corridor with up to four pieces a side and up to seven empty squares — 112 of them — and agrees on all 112.

Why the form stops at the corridor #

Put a gap inside one of the blocks and it breaks immediately.

$\texttt{TT..F}$ is worth $1$. $\texttt{T.T.F}$ is worth $\{2 \mid 1\}$. $\texttt{T..TF}$ is worth $2$.

All three have two toads, one frog and two empty squares. Any formula reading only those three counts would have to give one answer to all three, and the right answers are a whole number, a fight and a different whole number.

The reason is that an empty square behind a toad is not idle. When the leading toad advances it vacates a square, and the toad behind can advance into it — so a gap at the back feeds into the contested region at the front, one move at a time, and the arithmetic depends on where the gaps are and not merely on how many there are.

That kills the formula in the strongest available way. It is not that no simple formula has been found; it is that no function of the counts can exist, and three strips of five squares demonstrate it.

Playing one #

The figure names the outcome first and then invites the reader to try, which is this site’s habit and which is worth restating here for a specific reason: the strip is small enough to be solved completely, so the claim is exact rather than a strong opinion, and a reader who beats it has found an error in the recursion rather than a good move.

Where the values stop being tidy #

Thirty of the 6,561 eight-square strips are worth something with a star in it — $\{1\ast \mid \ast\}$, $\{2\ast \mid \ast\}$, $\{1\ast \mid -1\ast\}$ and a handful more.

Every one of them contains two separate contested regions. $\texttt{TT.FT.F}$ is a corridor and then another corridor, and each contributes a fight worth a move; the star is what a pair of odd contests leaves behind once the integer parts have been accounted for.

So the strips with stars are the ones that have already decomposed, and their values are sums of corridor values rather than anything new. That is a satisfying place for the exceptions to be, and it is the reason there are no exceptions of any other kind: 113 distinct values over 6,561 strips, all of them integers, switches with integer walls, or those two added together.

The value set, length by length #

The distinct values a strip can be worth grow slowly and in a shape worth noting: twelve at four squares, twenty-three at five, forty-one at six, seventy at seven, 113 at eight.

Each length roughly doubles the strip count and adds about forty per cent to the number of values. That is a collapse — 6,561 strips carrying 113 values, so an average of fifty-eight strips per value — and it is the same collapse every census on this site finds: the positions are many and the values are few.

The largest classes are the small integers. A strip worth nought is any arrangement in which the two sides have equal room and no contested odd gap, and there are a great many of those; a strip worth $\{2\ast \mid \ast\}$ is a specific arrangement of two corridors and there are very few.

That distribution has a practical reading. A player looking at a hopless strip is usually looking at a position worth a small integer, occasionally at one worth a fight, and rarely at anything else — which makes the game much easier to play well than to describe.

The arithmetic of a hopless strip #

Because pieces never pass each other, a strip decomposes in a way the hopping game does not, and it is worth stating as a rule of thumb even though the sweep shows it is not a theorem.

A toad immediately left of a frog is a wall: neither can ever move through the other, and the squares on the two sides of the wall are played independently from that moment. So a strip that has reached $\texttt{...T F...}$ in the middle is a sum of two shorter strips, and the values add.

The gaps between blocks work the other way. A gap with a frog on its left and a toad on its right is dead — the frog moves away leftward and the toad away rightward, and neither will ever enter it — so it separates the strip permanently.

Those two observations account for most of what happens on a board and they do not add up to a formula, for the reason the three five-square strips demonstrate: a gap behind a block is neither a wall nor dead, and it feeds moves into the contest at the front.

That combination — a game whose winner is easy to describe and whose values are not — is not peculiar to this one. The other partizan strip game here gives each player their own list of how much may be taken, and its outcomes fall into a period while its values do not; it is understood completely at the level of who wins and remains undescribed at the level of what a position is worth. Elephants and Rhinos is the same shape of answer arrived at from the other side: here it is the values that are simple, every one of them an integer or a fight between integers, and the description that is missing is which arrangement gets which.

What one clause was carrying #

The comparison is the cleanest instance on this site of a single rule clause deciding what kind of object a game’s values are.

With the hop: dyadic rationals with denominators up to eight, ups and downs, stars, switches with fractional walls — the full vocabulary, and no formula for a general strip despite fifty years of attention.

Without it: integers and switches with integer walls, plus stars where two contests meet. A closed form for corridors. And still no formula in general.

Both games are hard, and they are hard for different reasons. The hopping game is hard because its values are complicated. The hopless game is hard because the arrangement of the gaps matters and there are exponentially many arrangements, even though every individual value is simple.

That distinction is worth carrying. Solved and simple are different, and a game can have completely comprehensible values and no description of which position has which.

The name the other game has #

Toads and Frogs without the hop is a game in its own right and it has a name: Elephants and Rhinos, which is what Winning Ways calls the version where the two species can only shuffle and never pass. The renaming is not decoration — it is the authors’ way of saying that deleting the clause produces a different game rather than a variant of the same one, and the census above is the measurement that justifies the distinction.

Two hundred of the 729 strips of six squares have different values under the two rules. The other 529 agree, and they agree for a reason that is easy to miss: on a strip where no toad ever stands immediately left of a frog with an empty square beyond, the hop is never legal, so the two games are the same game and must give the same answer.

So the 200 are the positions where the clause can fire, and every one of them is a position in which a piece could have jumped. That is the cleanest possible statement of what a rule clause is worth: it changes exactly the positions in which it applies, and the count of those is the size of the change.

What a reader should take from the pair #

The two rungs together make an argument that neither makes alone.

Toads and Frogs has complicated values and no formula. Elephants and Rhinos has simple values and no formula. So the difficulty of describing the game is not caused by the complexity of its values — remove the complexity and the difficulty stays.

What causes it is the arrangement. A strip is a word over three letters, there are exponentially many words, and the value depends on the whole word rather than on any summary of it. That is a completely different obstacle from the values are hard to write down, and it is the one both games actually have.

Nothing worth fighting over makes the same point from the other end: Shove’s values are all numbers, every single one, and there is still no reading of a Shove position that produces its value. Simple values, no formula, and the reason is the same.

What one clause has to be doing for a whole number to come out #

The theorem waiting to be proved has a shape, and setting it out says why removing the hop is what produces it rather than merely simplifying things.

A position is worth a whole number when one player has a fixed count of moves and the other cannot interfere with them. Without the hop, a toad moves into the square in front of it and nothing else, so a toad’s future is a corridor: the empty squares ahead of it, in order, and no move by a frog can create or destroy one of them. A frog’s moves consume squares from the other end and the two counts share the same free squares, which is what makes the value a difference rather than two separate counts — but neither player can turn one of the other’s moves into two, or into none.

The hop is exactly the clause that breaks that. A hop crosses an occupied square, so a frog’s presence changes how far a toad travels in one move, which means a frog’s move can change a toad’s count. The moment a count depends on the opponent’s play it stops being a count and becomes a fight, and a fight is where the halves come from — a half is what one contested move is worth, and there is nothing for it to be contested about here.

So the statement to prove is not about values at all: it is that in a hopless strip, the number of moves each player has left is unaffected by the other’s play, on every position with no contested odd gap. From there the integer follows without any game theory, by the same one-line argument that makes an Amazons region owned by one player worth its free-square count.

That also predicts where the proof must fail, and the prediction matches the exception this page reports. A contested odd gap is precisely a place where the two players’ corridors overlap in a way parity cannot divide, and it is the one configuration where a move by one changes what the other can do.

What the sweep cannot say #

Eight squares. The 113 distinct values at that length are all integers, integer-walled switches, or those with a star; nothing rules out a ninth square producing something else, and the growth of the value set — twelve, twenty-three, forty-one, seventy, 113 — gives no sign of stopping.

Nothing here is a proof that the numbers are always integers. It is a count over 9,801 strips, which is every strip up to eight squares and is not every strip. The mechanism suggested above — that play is the consumption of empty squares and each is one move — is an argument rather than an induction, and turning it into one is the obvious next thing.

And the closed form is for corridors, which are a vanishing fraction of strips: 112 of the 9,801 swept. The general case has no formula here and the essay claims none.

Where the ladder goes next #

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

The rung above is the induction. Every number is a whole number is a theorem waiting to be proved, and 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.

Two neighbours are worth the trip. Nothing worth fighting over is the other game on this site whose values are all cold and readable in principle, where the reading also fails and fails differently. And the strip nobody has a formula for is the game with the clause restored, where the same question has been open for decades.