Working Backwards from the Goal

Start at the goal

You have two jugs with no markings, one holding 3 units and one holding 5, a tap, and a drain. You can fill a jug to the top, empty it, or pour one jug into the other until the first is empty or the second is full. The goal is exactly 4 units in the large jug.

Pouring at random can go on for a long time, because every state offers several moves. Working backwards turns the question round: instead of asking where a move leads, ask which state would give the answer in one more move.

What would produce it

Four is 5 − 1. So one way to finish is a full large jug that loses exactly 1 unit. Pouring the large jug into the small one moves as much as the small jug has room for, and the small jug has room for exactly 1 when it already holds 2, because 3 − 2 = 1.

So the state before the goal is 5 in the large jug and 2 in the small one. Write a state as (large, small): the goal is (4, 3), and the state before it is (5, 2).

That turns the problem into a smaller one: how do you get 2 into the small jug? Work backwards again. With the large jug empty, 2 in the small jug comes from pouring 2 across from the large jug; and 2 in the large jug, with the small jug empty, comes from filling the small jug from a full large one, which leaves 5 − 3 = 2, and then emptying the small jug.

Each state is (large, small). The four states on the left reach 4 in the large jug with one pour. The dashed two, (2, 2) and (3, 1), can never occur. The gold step is the one the lesson takes, from (5, 2).

Read it forward

The chain now reaches back to the empty jugs, so read it forward as the solution. Fill the large jug: (5, 0). Pour it into the small jug until that is full: (2, 3). Empty the small jug: (2, 0). Pour the 2 across: (0, 2).

Fill the large jug again: (5, 2). Pour it into the small jug, which takes only 1 unit: (4, 3). The large jug holds exactly 4.

The solution was found from the end, and it is written from the start. Every move in it is one of the three allowed moves, and each state follows from the one before it.

The amounts in the 5-unit and 3-unit jugs after each move. Six moves leave 4 in the large jug, and a search through every possible move finds no shorter way.

Why the search narrows

Searching forward, every state offers up to six moves (fill, empty or pour, with either jug), and most of them lead nowhere useful. Searching backward, only a few states could produce the goal at all.

Leaving aside states that already hold 4 in the large jug, exactly four states give 4 there after one pour: (5, 2), pouring into the small jug, and (1, 3), (2, 2) and (3, 1), pouring into the large one. Two of those can be crossed off at once. Every move leaves one jug empty or full: filling makes one full, emptying makes one empty, and a pour stops when the first jug is empty or the second is full. So (2, 2) and (3, 1) never occur.

The other survivor, (1, 3), also works, but it takes longer: fill the small jug, pour it into the large one, fill it again, pour until the large jug is full, leaving 1, empty the large jug, pour the 1 across, fill the small jug, and pour it in. That is 8 moves, against 6 for the route through (5, 2).

Undoing a chain of operations

A number is doubled, and then 7 is added, giving 23. Working forward means guessing the number. Working backward undoes the operations, the last one first: before 7 was added the number was 23 − 7 = 16, and before it was doubled it was 16 ÷ 2 = 8.

The order matters. Undoing in the original order, halving first and then taking 7 away, gives 23 ÷ 2 − 7 = 4.5, and 4.5 doubled plus 7 is 16, not 23. The last thing done is the first to undo, as the last layer put on is the first taken off.

Forward: 8 doubled is 16, and 16 + 7 = 23.

Backward: the same two steps undone in reverse order, each by its opposite, lead from 23 back to 8.

Finding a proof

Working backward is how many proofs are found. Suppose you want to prove that $a^2+b^2\ge 2ab$a² + b² ≥ 2ab for all numbers a and b. Ask what would give it: it would follow from $a^2-2ab+b^2\ge 0$a² − 2ab + b² ≥ 0. And that left side is ${\left(a-b\right)}^2$(a − b)², which is a square, and a square is never negative. The chain has reached something already known.

Now write the proof forward, from the known fact to the goal: ${\left(a-b\right)}^2\ge 0$(a − b)² ≥ 0, so $a^2-2ab+b^2\ge 0$a² − 2ab + b² ≥ 0, so $a^2+b^2\ge 2ab$a² + b² ≥ 2ab. Each line follows from the one before it.

Each backward step has to run forward as well. Here it does, because adding 2ab to both sides can be undone by taking it away. A step such as squaring both sides cannot always be undone: −3 and 3 have the same square. A chain found backward is a proof only once every link is checked in the forward direction.

The usual mistakes

Undoing in the wrong order. In the doubling puzzle, halving 23 before taking away 7 gives 4.5, not 8.

Writing up the backward chain as the proof. A proof that starts from $a^2+b^2\ge 2ab$a² + b² ≥ 2ab assumes what it sets out to prove. The steps are found from the goal and written from the hypothesis.

Stopping at a state that cannot be reached. (2, 2) would leave 4 in the large jug with one pour, but no sequence of moves ever produces it, so a chain that leads back to it is a dead end.

A culture and a dinner

In the first application below, a culture doubles each hour and then loses a harvest, so an hour is undone by adding the harvest back and then halving. In the second, a dinner time is fixed and every task is timed back from it.