Four Gallons From a Five and a Three, and Why Coprimality Is the Trick

You have a five gallon jug, a three gallon jug, neither of them marked, and a tap that never runs dry. Measure exactly four gallons.

The first thing most people do is add. Three, five, six, eight, nine, ten. Four is not on that list and never will be, and having established that, they stop. The list is correct. The conclusion drawn from it is not, and the gap between those two sentences is the whole problem.

The list of sums really does miss four

Write down every total you can build by filling jugs and adding: numbers of the form $3p + 5q$ with $p, q \ge 0$. You get

and the numbers missing from it are $1, 2, 4$ and $7$. Four is genuinely absent, so nobody who says so has made an arithmetic error. What they have done is answer a different question, because a pour is not an addition.

Emptying a jug subtracts. Pouring a full five into an empty three subtracts as well, and leaves two behind. Once subtraction is on the table, the set (1) is the wrong set to be looking at, because the reachable amounts are the integer combinations of three and five rather than the non-negative ones:

Read that equation as a shopping list. Ten gallons come out of the tap, six go down the drain, and four stay in the jug. The six pours below are exactly this arithmetic done with water.

Six pours, and why not five

Fill the five. Pour it into the three, which leaves two gallons behind. Empty the three, and pour those two gallons across. The three jug now holds two, so it has room for exactly one more. Refill the five, top the three up, and the one gallon that leaves the five takes it from five down to four.

The visible arithmetic is three subtractions, and the count of six comes from counting fills and emptyings as moves too: two fills, one emptying, three transfers. It is worth being clear about which you are counting, because an interviewer who hears "three" and expects six will assume you skipped something.

Six is also the minimum, and that is not something you can see by staring at the water. Draw the state graph: $(0,0)$ as the root, an edge for each legal move, and a breadth-first walk outward. Sixteen states are reachable out of the twenty-four pairs $(x,y)$ with $0 \le x \le 5$ and $0 \le y \le 3$, and the first one holding four gallons is $(4,3)$, at distance six. There is no shorter route because there is no shorter path in that graph.

The eight unreachable states are the ones where both jugs sit part full at the same time, and the reason is structural. Every legal move ends with the source emptied or the target filled, so one coordinate of the new state is always at an extreme. A candidate who notices this has found the invariant that makes the search finite, and it prunes a third of the grid for free.

The general pair of jugs

Nothing above used the numbers five and three except at the last step. What did the work is that they share no factor.

One direction is the invariant again. Every jug's contents starts at zero and changes only by $\pm a$, by $\pm b$, or by whatever the other jug can accept, so every amount that ever appears is an integer combination of $a$ and $b$, hence a multiple of $d$. The other direction is a classical identity: there exist integers $u, v$ with

and the shuttle of pours realises it, filling the small jug repeatedly and emptying the large one whenever it overflows. So for the five and the three, $d = 1$ and every whole number of gallons from one to five can be left in the big jug. Four is not special. It was chosen because it looks impossible.

The control case makes the role of $d$ concrete. Take jugs of six and four, whose greatest common divisor is two. Both start even, every capacity is even, so every reachable state has both jugs holding an even amount. Five gallons is therefore absent from the graph entirely rather than merely awkward to reach. Ten states are reachable out of thirty-five, and none of them contains an odd number.

The gaps in the sum list are a known object

The four numbers missing from (1), namely $1, 2, 4, 7$, are not a random shortfall. The set of non-negative combinations of two coprime numbers $a$ and $b$ misses finitely many integers, and the largest one it misses is

which for $a = 3$ and $b = 5$ gives $15 - 3 - 5 = 7$. Everything above seven is a sum of threes and fives, and the count of gaps is $(a-1)(b-1)/2 = 4$, which is exactly how many we found. So the reflex answer is standing on a real theorem. It just happens to be a theorem about the wrong semigroup.

Where the puzzle breaks

Two conditions are doing quiet work. The jugs must be unmarked, which has to mean no partial measurement by eye, otherwise you tip four gallons out of the five by inspection and the question evaporates. And the tap must be unlimited, since the route pulls ten gallons through to keep four.

There is also more than one solution. Filling the three twice into the five, emptying, and continuing gets you to four gallons in eight moves rather than six, which is why the answer is "six pours" and not "the six pours". If you are asked for a route, give one and say it is shortest; if you are asked whether it is shortest, the state graph is the argument, not the water.

Sources and further reading

• The identity behind equation (3) — Bézout's identity
• The gaps in (1) and the formula (4) — Numerical semigroup and the coin problem
• The puzzle family and its state-graph treatment — Water pouring puzzle

Every claim above was checked twice before publication: by exact arithmetic, and by an exhaustive breadth-first search over the whole state graph, which found the sixteen reachable states, confirmed that six moves is minimal, and confirmed that the six-and-four pair cannot produce an odd amount anywhere.