Our starting point is Problem Solving Through Recreational Mathematics by Bonnie Averbach and Orin Chein, especially page 118 of the edition shown here. The authors connect the jug problem to Diophantine equations by giving the coefficients a concrete meaning: fills minus empties to the outside. We revisit this method, apply it to 5- and 3-litre jugs to obtain 4 litres, and formalise it as an executable procedure. The interactive display and the cycle extension are teaching developments on this page, not quotations from the book.
Open the jug laboratory, one move at a time.
1. Rules first: what does measuring 4 litres mean?
We have a source, a drain and two unmarked jugs. For the book’s counting method, our moves are: fill an empty jug, empty a full jug into the drain, or pour until the source jug is empty or the receiving jug is full. We never stop a pour by eye. The laboratory uses exactly these rules.
The goal is to leave the requested amount in one jug, with the other empty. Merely saying ‘4 litres in the larger jug’ could leave more water in the smaller one: that is a different problem. Filling or emptying partly full jugs, allowed in other versions, cannot simply be counted as contributions of a whole capacity.
2. The book’s problem: 3 and 5 to obtain 1
The book states this example in gallons. Here we use the same numerical pattern in litres: this is not a unit conversion, but a problem with proportional capacities and the same procedure.
In this first example, A holds 3 litres and B holds 5. Write 3x + 5y = 1. The book proposes (x,y) = (2,-1): take two 3-litre jugfuls and return one 5-litre jugful. The pours make the order of operations possible.
| Step | Operation | State (A, B) | x | y | Total balance |
|---|---|---|---|---|---|
| 0 | Start: both empty | (0,0) | 0 | 0 | 3 × (0) + 5 × (0) = 0 |
| 1 | Fill A from the source: 3 L | (3,0) | 1 | 0 | 3 × (1) + 5 × (0) = 3 |
| 2 | Pour from A into B: 3 L | (0,3) | 1 | 0 | 3 × (1) + 5 × (0) = 3 |
| 3 | Fill A from the source: 3 L | (3,3) | 2 | 0 | 3 × (2) + 5 × (0) = 6 |
| 4 | Pour from A into B: 2 L | (1,5) | 2 | 0 | 3 × (2) + 5 × (0) = 6 |
| 5 | Empty B into the drain: 5 L | (1,0) | 2 | -1 | 3 × (2) + 5 × (-1) = 1 |
Here x increases only when we take 3 litres from the source; y decreases only when we discharge 5 litres. Pouring A into B is not emptying A into the drain: neither x nor y changes. At the end, 3 × 2 + 5 × (-1) = 1.
3. States and coefficients: two different records
From now on we use A = 5 litres and B = 3 litres. The state (u,v) gives the actual contents of A and B. Instead, x = fills of A - empties of A into the drain and y = fills of B - empties of B into the drain. Both jugs always start empty.
At every step, 5x + 3y = u + v: water taken minus water returned equals water remaining. A pour changes u and v, but not x and y. Negative coefficients do not mean negative water: they record more empties than fills for that jug.
To obtain (4,0), the final balance must therefore be 5x + 3y = 4. The equation alone specifies neither the order of moves nor which jug contains the water.
4. From the equation to the family of solutions
5 = 1 × 3 + 2 and 3 = 1 × 2 + 1, so GCD(5,3) = 1. Back-substitution gives 1 = 2 × 3 - 5. Multiply by 4: 4 = 8 × 3 - 4 × 5, giving the particular solution (-4,8).
All integer solutions are x = -4 + 3k and y = 8 - 5k, with k ∈ ℤ. For k = 1 we obtain (-1,3); for k = 2, (2,-2). We now translate both, without treating the coefficients as an already ordered list of moves.
Explore the general method
The general Diophantine-equation method, with theory and example · General laboratory for ax + by = c.
5. Three fills of the smaller jug, one empty of the larger
The solution (x,y) = (-1,3) says 4 = -5 + 3 × 3. The 3-litre jug B supplies the pours; the 5-litre jug A receives the water. Empty A when it is full; refill B from the source when it is empty.
| Step | Operation | State (A, B) | x | y | Total balance |
|---|---|---|---|---|---|
| 0 | Start: both empty | (0,0) | 0 | 0 | 5 × (0) + 3 × (0) = 0 |
| 1 | Fill B from the source: 3 L | (0,3) | 0 | 1 | 5 × (0) + 3 × (1) = 3 |
| 2 | Pour from B into A: 3 L | (3,0) | 0 | 1 | 5 × (0) + 3 × (1) = 3 |
| 3 | Fill B from the source: 3 L | (3,3) | 0 | 2 | 5 × (0) + 3 × (2) = 6 |
| 4 | Pour from B into A: 2 L | (5,1) | 0 | 2 | 5 × (0) + 3 × (2) = 6 |
| 5 | Empty A into the drain: 5 L | (0,1) | -1 | 2 | 5 × (-1) + 3 × (2) = 1 |
| 6 | Pour from B into A: 1 L | (1,0) | -1 | 2 | 5 × (-1) + 3 × (2) = 1 |
| 7 | Fill B from the source: 3 L | (1,3) | -1 | 3 | 5 × (-1) + 3 × (3) = 4 |
| 8 | Pour from B into A: 3 L | (4,0) | -1 | 3 | 5 × (-1) + 3 × (3) = 4 |
This takes 8 moves: three fills of B, one empty of A and four pours. At (1,3) we already have 4 litres in total, but split between the jugs: the last pour is needed to obtain (4,0).
6. Two fills of the larger jug, two empties of the smaller
The solution (x,y) = (2,-2) says 4 = 2 × 5 - 2 × 3. This time we fill A and pour into B, emptying B whenever it is full.
| Step | Operation | State (A, B) | x | y | Total balance |
|---|---|---|---|---|---|
| 0 | Start: both empty | (0,0) | 0 | 0 | 5 × (0) + 3 × (0) = 0 |
| 1 | Fill A from the source: 5 L | (5,0) | 1 | 0 | 5 × (1) + 3 × (0) = 5 |
| 2 | Pour from A into B: 3 L | (2,3) | 1 | 0 | 5 × (1) + 3 × (0) = 5 |
| 3 | Empty B into the drain: 3 L | (2,0) | 1 | -1 | 5 × (1) + 3 × (-1) = 2 |
| 4 | Pour from A into B: 2 L | (0,2) | 1 | -1 | 5 × (1) + 3 × (-1) = 2 |
| 5 | Fill A from the source: 5 L | (5,2) | 2 | -1 | 5 × (2) + 3 × (-1) = 7 |
| 6 | Pour from A into B: 1 L | (4,3) | 2 | -1 | 5 × (2) + 3 × (-1) = 7 |
| 7 | Empty B into the drain: 3 L | (4,0) | 2 | -2 | 5 × (2) + 3 × (-2) = 4 |
This route takes 7 moves. At step 6 the state is (4,3): the larger jug contains the requested amount, but the balance is still 5 × 2 + 3 × (-1) = 7. Only after emptying B do we reach (4,0) and the solution (2,-2).
7. A systematic procedure, not a sequence of guesses
We turn the book’s interpretation into an operational algorithm. Choose a direction, say A → B, and start at (0,0):
- If one jug contains the target and the other is empty, stop.
- If one contains the target and the other is full, empty the full one and stop.
- Otherwise, if B is full, empty it.
- If A is empty, fill it from the source.
- In all other cases, pour
min(u, b - v)litres from A into B, then repeat.
Direction B → A exchanges the roles. Each move follows from the state, not intuition. We first check the GCD and capacity: if the target is admissible, the procedure reaches it. Successive remainders traverse the multiples of the GCD; the capacities divided by the GCD are coprime.
The laboratory shows both directions and their actual counts. These are constructive routes: we do not attribute our interface or an automatic minimum search to the book.
8. What about the other integer solutions? Add zero-balance cycles
The family is infinite, but there are finitely many jug states: more distant solutions may include repetitions. A cycle from (0,0) back to (0,0), filling B and emptying A, takes five 3-litre jugfuls and returns three 5-litre jugfuls. Its contribution is (Δx,Δy) = (-3,5) and 5 × (-3) + 3 × 5 = 0.
Following this cycle with the route for (-1,3) gives (-4,8): the same final water, more operations. The reverse cycle contributes (3,-5). In general the increments are (b/g,-a/g) or their opposites, where g = GCD(a,b).
Choose k in the laboratory: it constructs a route with exactly those coefficients by adding the required number of closed cycles before the final route. Playback is limited to 2,000 moves for readability; a display limit is not mathematical impossibility.
9. When it can be done, and when it cannot
For positive integer capacities a and b and target c, isolating c litres is possible exactly when GCD(a,b) ∣ c and 0 ≤ c ≤ max(a,b), with a source and drain. Divisibility concerns the equation; the bound concerns the final container. If c = 0, do nothing.
4x + 6y = 1: impossible, since the GCD is 2 and does not divide 1.- With 4 and 6, obtaining 2 is possible:
(0,0) → (0,6) → (4,2) → (0,2). - With 5 and 3, the equation for 8 has integer solutions, but neither jug can hold 8 litres alone.
- With 6 and 10, obtain 8 via
(0,0) → (0,10) → (6,4) → (0,4) → (4,0) → (4,10) → (6,8) → (0,8). The balance is2 × 10 - 2 × 6 = 8. - With 2 and 7, obtain 1 via
(0,0) → (0,7) → (2,5) → (0,5) → (2,3) → (0,3) → (2,1) → (0,1). - With 6 and 9, obtaining 4 is impossible: the GCD is 3.
Each sequence follows the order of the capacities just stated. In the laboratory, A and B stay fixed even when A is the smaller jug.
10. A correct solution need not be the shortest
For 5 and 3, the 7-move route is shorter than the 8-move route. Minimising |x| + |y| is not enough: it is 4 for both pairs, but the number of pours differs. If the other jug may stay full, 6 moves suffice: that is a different target.
To certify a minimum, use breadth-first search (BFS) on the state graph, counting each fill, empty or pour as one move. This algorithmic check is distinct from the counting method. The laboratory reports the lengths of its displayed routes without automatically calling them optimal.
11. The closed 8–5–3 variant is another model
If the 8-litre container starts full and there is no source or drain, only pours remain. To split the 8 litres into two lots of 4, ordering states as (8,5,3), one route is:
(8,0,0) → (3,5,0) → (3,2,3) → (6,2,0)
→ (6,0,2) → (1,5,2) → (1,4,3) → (4,4,0)The total is always 8: the interpretation of withdrawals and discharges in the open model cannot be transferred unchanged. The new laboratory concerns two jugs with a source and drain.
12. Reading the laboratory’s two bars
Both bars share the same scale in litres: the 5-litre jug is taller than the 3-litre jug. The outline marks capacity; coloured water marks current contents. Below are the state, x and y, water taken and water discharged. The balance is checked at every move.
Press Next for one operation, Previous to review it, or play automatically at one move per second. Change direction, choose k or return to the start. The table contains the whole route and distinguishes cycles from the final part.
The takeaway is simple: the equation tells us how much; the procedure builds how; the states verify that every move is legal.