The River-Crossing Shuttle, math that surprises you lesson

Two adults and two children stand on the left bank of a river with one small boat. The boat can carry one adult alone, or one or two children, but never an adult together with a child. How can all four reach the right bank, and how few crossings does it take? An adult who rows across first is stuck there with the boat, so the plan has to arrange who brings the boat back. This page describes the puzzle as a set of states, builds a solution of nine crossings from a repeatable shuttle, and shows that no plan is shorter.

Key terms

River crossing puzzle

Definition A river crossing puzzle asks for a group to be carried from one bank of a river to the other in a boat, under rules that limit who may ride together and, in some puzzles, who may be left together on a bank. A solution is a sequence of crossings that ends with everyone on the far bank. In the version on this page, two adults and two children start on the left bank with the boat. Each crossing carries one adult alone, one child alone or both children, so an adult never rides with a child and two adults never ride together. Anyone may row, the boat never crosses empty, and it always leaves from the bank where it is. There is no rule about who may wait together on a bank. The goal is to have all four people on the right bank. The puzzle can be solved in nine crossings, and no solution uses fewer.

In plain words The boat has to keep coming back, and somebody has to bring it. An adult who crosses can only take the boat straight back again, so a child has to be waiting on the far bank to return it instead.

Example Call the adults A and B and the children X and Y. The nine crossings below solve the puzzle, and the boat is always on the bank where its last riders got off.

Crossing	Who rides	Left bank after	Right bank after
1	X and Y, to the right	A, B	X, Y and the boat
2	X, to the left	A, B, X and the boat	Y
3	A, to the right	B, X	A, Y and the boat
4	Y, to the left	B, X, Y and the boat	A
5	X and Y, to the right	B	A, X, Y and the boat
6	X, to the left	B, X and the boat	A, Y
7	B, to the right	X	A, B, Y and the boat
8	Y, to the left	X, Y and the boat	A, B
9	X and Y, to the right	nobody	A, B, X, Y and the boat

Every crossing carries one adult alone, one child alone or both children, so every crossing is legal.

State space

Definition A state of a river crossing puzzle records which bank each person is on and which bank the boat is on. Nothing else affects what can happen next, so two moments with the same state have exactly the same possible continuations. The state space is the set of all states, together with the legal crossings, each of which leads from one state to another. A solution is then a path through the state space from the start state to the goal state, and a solution with the fewest crossings is a shortest such path. With $p$ people there are $2^p$ ways to place them on the two banks and two places for the boat, so there are $2^{p + 1}$ states.

In plain words A state is a snapshot of who is where. The state space is a map of all the snapshots, with an arrow for every crossing the rules allow.

Example With A, B, X and Y there are $2^4 \cdot 2 = 32$ states. Sending an adult across first leads from the start state to the state with that adult and the boat on the right. From there the only legal crossing is the same adult rowing back, which leads to the start state again, so those two crossings make no progress. The first four crossings of the solution also bring both children and the boat back to the left bank, but they end in a different state, with A on the right and B, X, Y and the boat on the left. Searching the state space level by level, first every state one crossing from the start, then every state two crossings away, and so on, finds no route to the goal with fewer than nine crossings.

Legal state

Definition A legal state is a state that the rules of the puzzle allow. Rules about who may ride together limit the crossings, while rules about who may be left together limit the states. In the classic puzzle of a farmer with a wolf, a goat and a cabbage, where only the farmer rows and the boat holds the farmer and at most one of the three, a state is not legal if the wolf is left with the goat, or the goat with the cabbage, on a bank without the farmer. The adults and children puzzle has no rule of that kind. Its states are limited only by the boat, because the boat never crosses empty, so the people who last rode in it are on the bank where it lies. A state with the boat on a bank where nobody stands can therefore never occur. Of the $32$ states, the $30$ in which the boat’s bank holds at least one person are legal, and each of these $30$ can be reached from the start.

In plain words A legal state is a snapshot that the rules permit. A puzzle can forbid certain snapshots, certain crossings or both, and the rules of the adults and children puzzle only restrict the crossings.

Example The state with A on the right and B, X, Y and the boat on the left is legal, and the solution reaches it after four crossings. The state with all four people on the left and the boat on the right is not, because nobody could have taken the boat there. In the farmer’s puzzle the legal states decide the first trip. If the farmer crosses alone or takes the cabbage, the wolf and the goat are left together, and if the farmer takes the wolf, the goat and the cabbage are left together. Only the trip with the goat leads to a legal state.

Shuttle strategy

Definition In the adults and children puzzle with $m$ adults and two children, under the same boat rules, the shuttle strategy repeats a block of four crossings. Both children cross, one child returns, one adult crosses, and the other child returns. Each block moves one adult to the right bank for good and ends with both children and the boat back on the left bank, so the same block can be used again. After $m$ blocks the two children cross together, for a total of $4m + 1$ crossings. No plan under these rules uses fewer crossings.

In plain words The two children run a ferry. Each time, they leave one of themselves on the far bank, so that someone is there to bring the boat back after an adult crosses.

Example With two adults the shuttle uses $4 \cdot 2 + 1 = 9$ crossings, the solution in the table above. With three adults it uses $13$ crossings and with four adults $17$ .

To see that no plan is shorter, take any solution and let $f$ be its number of crossings to the right. The boat starts on the left and ends on the right, so there are $f - 1$ crossings back. Each crossing to the right carries one or two people, and two only when both children ride. If $p$ of the crossings to the right carry two people, these crossings carry $f + p$ riders in all, while the crossings back carry at least $f - 1$ riders. The difference is the number of people moved, $m + 2$ , so

\begin{aligned} m + 2 &\le (f + p) - (f - 1) \\[0.4em] &= p + 1, \end{aligned}

and $p \ge m + 1$ . Each adult has to cross to the right at least once, alone, so at least $m$ crossings to the right carry an adult, and they are different from the $p$ crossings that carry both children. So $f \ge 2m + 1$ , and the total number of crossings, $2f - 1$ , is at least $4m + 1$ . For two adults this gives at least $9$ crossings, so the shuttle is as short as possible.

Check yourself

A third adult C joins A and B, with the same two children and the same boat. Use the shuttle to get everyone across. How many crossings does it take, and what does the left bank look like after each block?

Show the answer

Each adult needs one block of four crossings. X and Y cross, X returns, A crosses and Y returns, which leaves B, C, X, Y and the boat on the left. The same block for B leaves C, X, Y and the boat on the left, and the block for C leaves only X, Y and the boat. Finally X and Y cross together. The total is

4 \cdot 3 + 1 = 13

crossings, and by the counting argument under the shuttle strategy, with $m = 3$ , no plan for three adults and two children uses fewer.

Now suppose there are two adults but only one child, with the same boat rules. Can everyone reach the right bank?

Show the answer

No. With one child, every legal crossing carries exactly one person, an adult alone or the child alone. From the start, the first crossing puts one person and the boat on the right. The only person who can then take the boat back is that same person, and doing so returns to the start state. So the only states that can ever be reached are the start state and the three states with a single person and the boat on the right bank. The goal is not among them. The shuttle needs a second child who stays behind on the far bank while the first one rows back.

Change the rules so that the boat may also carry one adult together with one child, though still never two adults. Find a plan with five crossings for two adults and two children, and show that no plan uses fewer.

Show the answer

A and X cross, and X returns. B and X cross, and X returns. Then X and Y cross. After the second crossing A is on the right, after the fourth A and B are on the right with X, Y and the boat on the left, and the fifth crossing finishes. That is five crossings.

No plan is shorter. Each crossing to the right carries at most two people and each crossing back at least one, so with $f$ crossings to the right the number of people moved is at most $2f - (f - 1) = f + 1$ . Four people must be moved, so $f + 1 \ge 4$ , which gives $f \ge 3$ and at least $2f - 1 = 5$ crossings. The old argument for $4m + 1$ no longer applies, because an adult no longer has to cross alone.