Frogs and Toads, math that surprises you lesson

Seven stones lie in a row with the middle one empty. Three frogs stand on the left three stones facing right, and three toads stand on the right three stones facing left. Each animal may only move forward, either by sliding onto the empty stone in front of it or by jumping over one animal of the other kind onto the empty stone just beyond. Can the frogs and the toads swap sides, and what is the smallest number of moves that does it? This page counts what every solution must contain, which shows that any solution takes exactly 15 moves, and then gives a route that does it in 15.

Key terms

Frogs and toads puzzle

Definition The frogs and toads puzzle with $n$ animals of each kind, where $n \ge 1$ , uses a row of $2n + 1$ stones numbered from left to right. At the start, $n$ frogs stand on stones $1$ to $n$ , $n$ toads stand on stones $n + 2$ to $2n + 1$ , and stone $n + 1$ is empty. Each stone holds at most one animal, so exactly one stone is empty at every moment. Frogs only ever move to the right and toads only to the left, one animal per move. A move is either a slide, in which an animal moves onto the empty stone directly in front of it, or a jump, in which an animal passes over the stone directly in front of it, which must hold an animal of the other kind, and lands on the empty stone just beyond. Nobody moves backward, jumps over an animal of its own kind or jumps over more than one stone. Any animal with a legal move may make it, so frogs and toads do not have to take turns. The goal is to have toads on stones $1$ to $n$ , frogs on stones $n + 2$ to $2n + 1$ and stone $n + 1$ empty again. The puzzle can be solved for every $n$ , and every solution contains exactly $n^2$ jumps and $2n$ slides, so every solution has

n^2 + 2n = (n + 1)^2 - 1

moves. Some sequences of legal moves get stuck before reaching the goal, so a solution still has to be planned.

In plain words Frogs hop right, toads hop left, and nobody turns back. Every frog has to get past every toad, and the only way to get past is to jump. All solutions have the same length, but a careless move can leave every animal blocked.

Example Write F for a frog, T for a toad and $\square$ for the empty stone. With one of each kind the row is $\mathrm{F\,\square\,T}$ . The frog slides, the toad jumps over it, and the frog slides again, which gives $\mathrm{\square\,F\,T}$ , then $\mathrm{T\,F\,\square}$ , then $\mathrm{T\,\square\,F}$ . That is $3 = 1^2 + 2 \cdot 1$ moves. With two of each kind, the eight moves in the table solve the puzzle.

Move	What happens	Stones 1 to 5 after the move
1	The frog on stone 2 slides to stone 3	$\mathrm{F\,\square\,F\,T\,T}$
2	The toad on stone 4 jumps to stone 2	$\mathrm{F\,T\,F\,\square\,T}$
3	The toad on stone 5 slides to stone 4	$\mathrm{F\,T\,F\,T\,\square}$
4	The frog on stone 3 jumps to stone 5	$\mathrm{F\,T\,\square\,T\,F}$
5	The frog on stone 1 jumps to stone 3	$\mathrm{\square\,T\,F\,T\,F}$
6	The toad on stone 2 slides to stone 1	$\mathrm{T\,\square\,F\,T\,F}$
7	The toad on stone 4 jumps to stone 2	$\mathrm{T\,T\,F\,\square\,F}$
8	The frog on stone 3 slides to stone 4	$\mathrm{T\,T\,\square\,F\,F}$

There are four jumps and four slides, and $8 = 2^2 + 2 \cdot 2$ . If instead both frogs slide at the start, the row becomes $\mathrm{\square\,F\,F\,T\,T}$ and no animal can move, because the empty stone is behind both frogs and more than two stones ahead of each toad.

Counting argument

Definition A counting argument proves a fact about every solution of a puzzle at once by keeping count of some quantity. One chooses a quantity whose values at the start and at the goal are known and finds exactly how much each kind of move can change it. Every solution has to change the quantity by the full difference, which limits how many moves of each kind it can contain. The argument covers all solutions, including ones nobody has written down, but it does not show that a solution exists.

In plain words Instead of trying routes one after another, keep score of something that has to change between the start and the goal, and ask how much a single move can change it.

Example In the frogs and toads puzzle with $n$ of each kind, pair every frog with every toad, which gives $n \cdot n = n^2$ pairs. At the start the frog of each pair is to the left of its toad, and at the goal it is to the right. A slide passes nobody, so it changes the order of no pair. A jump passes exactly one animal of the other kind, so it reverses the order of exactly one pair. A frog that has passed a toad can never fall behind it again, because frogs only move right and toads only move left. So each pair is reversed exactly once, and every solution has exactly $n^2$ jumps.

Now count distance. Frogs never pass one another, so the frog that starts on stone $k$ ends on stone $k + n + 1$ , and the frogs travel $n(n + 1)$ stones in all. The toads travel the same distance to the left, so all the animals together travel $2n(n + 1)$ stones. A slide covers one stone and a jump covers two, so a solution with $S$ slides satisfies

2n^2 + S = 2n(n + 1),

which gives $S = 2n$ . For three of each kind there are $9$ pairs, so $9$ jumps, and $24$ stones of travel. The jumps cover $18$ of them, which leaves $6$ slides and $15$ moves in total.

Lower bound

Definition A lower bound for a quantity is a number that the quantity is proved never to be less than. A lower bound $L$ for the number of moves in a puzzle means that every solution uses at least $L$ moves. It does not claim that a solution exists, and it does not claim that some solution uses exactly $L$ moves. A lower bound that the quantity actually reaches is called sharp.

In plain words A lower bound rules out doing better than some number. It does not promise that anyone can do that well.

Example For three of each kind, each count on its own gives a lower bound. The animals must travel $24$ stones and no move covers more than $2$ , so every solution has at least $12$ moves. Nine pairs must be reversed and no move reverses more than one, so every solution has at least $9$ moves. Both statements are true, but neither bound is sharp, because no solution has $9$ or $12$ moves. Combining the two counts gives the bound of $15$ , since the $9$ jumps cover only $18$ of the $24$ stones and the remaining $6$ stones need $6$ slides. That bound is sharp, as the route of $15$ moves below shows.

Minimum number of moves

Definition The minimum number of moves of a puzzle is the smallest number of moves among all its solutions. It exists only when the puzzle has at least one solution. Proving that the minimum is $M$ takes two facts, a lower bound showing that no solution uses fewer than $M$ moves, and a construction, which is a legal solution that uses exactly $M$ moves. For the frogs and toads puzzle with $n$ of each kind the minimum is $n^2 + 2n$ . In this puzzle every solution has that length, so the minimum is also the only possible length.

In plain words A count can show how short a solution would have to be, but only an actual route shows that such a solution is there to be found.

Example For three of each kind, start from $\mathrm{F\,F\,F\,\square\,T\,T\,T}$ and let the two kinds move in runs, first the frogs, then the toads, and so on, with $1, 2, 3, 3, 3, 2$ and $1$ moves in the runs. At every move of a run, the kind whose turn it is has exactly one legal move, so the runs fix the route.

Run	Who moves	Moves	Stones 1 to 7 after the run
1	frogs	slide	$\mathrm{F\,F\,\square\,F\,T\,T\,T}$
2	toads	jump, slide	$\mathrm{F\,F\,T\,F\,T\,\square\,T}$
3	frogs	jump, jump, slide	$\mathrm{\square\,F\,T\,F\,T\,F\,T}$
4	toads	jump, jump, jump	$\mathrm{T\,F\,T\,F\,T\,F\,\square}$
5	frogs	slide, jump, jump	$\mathrm{T\,\square\,T\,F\,T\,F\,F}$
6	toads	slide, jump	$\mathrm{T\,T\,T\,F\,\square\,F\,F}$
7	frogs	slide	$\mathrm{T\,T\,T\,\square\,F\,F\,F}$

The route has $9$ jumps and $6$ slides, so it meets the lower bound of $15$ , and $15$ is the minimum. In the middle of the route the empty stone sits at the far left with the animals alternating, and three toad jumps in a row carry it to the far right. The same pattern of runs, $1, 2, \dots, n$ , then $n$ twice more, then $n - 1$ down to $1$ , solves the puzzle for every $n$ . Its length is

\begin{aligned} &\frac{n(n + 1)}{2} + 2n + \frac{n(n - 1)}{2} \\[0.4em] &\quad = n^2 + 2n. \end{aligned}

Check yourself

Four frogs and four toads stand on nine stones with the middle stone empty. How many jumps, slides and moves does a solution have, and do runs of $1, 2, 3, 4, 4, 4, 3, 2$ and $1$ moves have the right total?

Show the answer

There are $4 \cdot 4 = 16$ frog and toad pairs, so a solution has $16$ jumps. Each frog ends $5$ stones to the right of where it started, so the frogs travel $20$ stones, and the toads travel another $20$ to the left. The jumps cover $32$ of these $40$ stones, which leaves $8$ slides. A solution therefore has

16 + 8 = 24

moves, in agreement with $4^2 + 2 \cdot 4 = 24$ and with $(4 + 1)^2 - 1 = 24$ . The runs add up to $1 + 2 + 3 + 4 + 4 + 4 + 3 + 2 + 1 = 24$ , as they should.

Change the rules so that an animal may also move backward, by sliding back onto the empty stone directly behind it or by jumping back over one animal of the other kind. Jumping over an animal of the same kind is still forbidden. With three of each kind, is $15$ still the minimum, and does every solution still have $15$ moves?

Show the answer

The minimum is still $15$ , but solutions can now be longer. Count forward and backward moves separately, with $j_f$ and $j_b$ forward and backward jumps and $s_f$ and $s_b$ forward and backward slides. Call a pair finished when its frog is to the right of its toad. A forward jump finishes one pair and a backward jump undoes one, while slides change no pair, and the number of finished pairs goes from $0$ to $9$ . So $j_f - j_b = 9$ . Measured in each animal’s forward direction, the animals still have to travel $24$ stones in net, so $2(j_f - j_b) + (s_f - s_b) = 24$ , which gives $s_f - s_b = 6$ . The number of moves is then

\begin{aligned} &j_f + j_b + s_f + s_b \\[0.4em] &\quad = 15 + 2(j_b + s_b). \end{aligned}

Every solution therefore has at least $15$ moves, and the old route of $15$ moves is still legal, so $15$ is still the minimum. Backward moves only add to the count. For example, the frog on stone $3$ can slide forward to stone $4$ and straight back, and the old route then takes $15$ more moves, for $17$ in all. The counting argument still gives a sharp lower bound, but it no longer fixes the length of every solution.

Extend the puzzle to unequal groups. Three frogs stand on stones $1$ to $3$ , stone $4$ is empty, and two toads stand on stones $5$ and $6$ . The goal is toads on stones $1$ and $2$ , stone $3$ empty and frogs on stones $4$ to $6$ . Count the jumps, slides and moves, find a route, and give the count for $m$ frogs and $n$ toads.

Show the answer

There are $3 \cdot 2 = 6$ frog and toad pairs, so a solution has $6$ jumps. The frog that starts on stone $k$ ends on stone $k + 3$ , so the frogs travel $3 \cdot 3 = 9$ stones, and the toad that starts on stone $k$ ends on stone $k - 4$ , so the toads travel $2 \cdot 4 = 8$ stones. The jumps cover $12$ of the $17$ stones, which leaves $5$ slides and $11$ moves.

One route uses runs of $1, 2, 3, 2, 2$ and $1$ moves, starting with the frogs. The frog on stone $3$ slides. The toads jump and slide. The frogs jump, jump and slide, which gives $\mathrm{\square\,F\,T\,F\,T\,F}$ . The toads jump twice, the frogs slide and jump, and a toad slides, which ends at $\mathrm{T\,T\,\square\,F\,F\,F}$ after $11$ moves.

With $m$ frogs and $n$ toads there are $mn$ jumps. The frogs travel $m(n + 1)$ stones and the toads $n(m + 1)$ , so the slides number $m(n + 1) + n(m + 1) - 2mn = m + n$ . The number of moves is

\begin{aligned} &mn + m + n \\[0.4em] &\quad = (m + 1)(n + 1) - 1, \end{aligned}

which is $11$ for three frogs and two toads and $n^2 + 2n$ when $m = n$ .