Two Jugs, One Equation: From the 3–5 Puzzle to Bézout

Two unmarked jugs, a water source, and a precise goal: measure an amount that is not printed on either container. The puzzle is physical, yet it leads naturally to integers, the greatest common divisor, Bézout’s identity, and graph algorithms.

The arithmetic criterion tells us whether the target passes the divisibility test; capacity bounds and jug states determine whether and how it can be realized physically. These are different and complementary answers.

1. Rules and goal

In the classic open model, we have an unlimited water source, a drain, and two unmarked jugs with integer capacities. A legal move is exactly one of the following:

• fill one jug completely from the source;
• empty one jug completely into the drain;
• pour from one jug into the other until the first is empty or the second is full.

A pour cannot be stopped by eye. In the main problem the capacities are 3 and 5 litres, and the strict goal is (1,0): one litre in the 3-litre jug and an empty 5-litre jug. We always write a state as (u,v), where u is the content of the 3-litre jug and v is the content of the 5-litre jug.

2. The 3–5 case, state by state

From empty jugs to one isolated litre

Step	Move	State	Result of the move
0	Start	(0,0)	Both jugs are empty
1	Fill the 3-litre jug	(3,0)	The jug is full
2	Pour from 3 into 5	(0,3)	The 3-litre jug becomes empty
3	Fill the 3-litre jug again	(3,3)	The jug is full
4	Pour from 3 into 5	(1,5)	Only 2 litres fit in the 5-litre jug
5	Empty the 5-litre jug	(1,0)	The required litre remains isolated

(0,0) → (3,0) → (0,3) → (3,3) → (1,5) → (1,0)

Every arrow follows the rules, and every coordinate remains between zero and the corresponding capacity. These two simple checks expose many false solutions.

3. State, balance, and invariant

It is useful to keep two records. The physical state says where the water is; the balance says how much water is present in total and how it entered or left. Along the route above:

Physical state and external balance

State	Total present	External balance
(0,0)	0	0
(3,0)	3	3
(0,3)	3	3
(3,3)	6	2 · 3
(1,5)	6	2 · 3
(1,0)	1	2 · 3 − 5

During a pour, the total u + v is invariant: only its distribution changes. Filling and emptying exchange water with the outside. On this route, two complete 3-litre jugfuls enter and one complete 5-litre jugful leaves, hence:

1 = 2 · 3 − 5

There is a more general arithmetic invariant: every reachable volume is an integer combination of the capacities. At the start there is only zero; filling introduces a capacity, emptying introduces zero, and a pour produces sums or differences with a capacity when one jug empties or the other fills. Integer combinations therefore remain closed under every legal move.

The coefficient pair is neither the physical state nor unique. It is an algebraic label that certifies a volume; the state (u,v) remains the essential physical description.

4. What negative coefficients mean

The route gives a Diophantine equation, meaning an equation whose solutions are required to be integers:

3x + 5y = 1,
x = 2, y = −1.

The coefficient −1 does not represent a negative amount of water. In the balance it records that one complete 5-litre jugful was returned to the drain. Coefficients count signed contributions; actual jug contents always remain between zero and their capacities.

This interpretation as a net count is direct for canonical routes, in which a jug is filled only when empty and drained only when full. If a partly filled jug is filled or emptied, the coefficients remain an algebraic certificate, but they no longer equal a simple count of operations.

This distinction prevents a common misunderstanding: an integer solution of the equation is an arithmetic certificate, not yet an automatic list of fills and pours. To obtain the moves, we must construct a path through legal states.

5. The extended Euclidean algorithm and Bézout’s identity

The greatest common divisor of two positive integers is the largest positive integer that divides both of them. The Euclidean algorithm finds it; tracing its divisions backwards also produces Bézout coefficients:

5 = 1 · 3 + 2
3 = 1 · 2 + 1

1 = 3 − 2
  = 3 − (5 − 3)
  = 2 · 3 − 5

We have recovered exactly the balance of the route. Bézout’s identity states that, for positive integers a and b, integers r and s exist such that:

a r + b s = GCD(a,b)

Multiplying the identity by an integer produces every target that is a multiple of the GCD. For 3x + 5y = 1, starting with (2,−1), all integer solutions are:

x = 2 + 5t
y = −1 − 3t,  where t is an integer.

This algebraic infinity does not imply infinitely many physical states: jug capacities are finite, and many coefficient pairs describe the same volume without suggesting a convenient route.

6. The general rule and its limits

For capacities a and b and target d, the associated equation is:

a x + b y = d

Let g = GCD(a,b). The equation has integer solutions if and only if g divides d. In the classic open model, to leave exactly d litres in one jug while the other is empty, we also need:

0 ≤ d ≤ max(a,b).

With the standard moves, the two conditions are also sufficient. Divisibility rules out arithmetically impossible targets; the capacity bound rules out targets that fit in neither jug. The equation ax + by = d concerns the total present: to set it equal to d, the other jug must really be empty at the end. If we stopped with d in one jug and more water in the other, the total would not be d.

7. The 4–6 comparison: one litre no, two litres yes

For 4- and 6-litre jugs, GCD(4,6) = 2. Every combination 4x + 6y is even, so one litre is impossible. There is no need for random trial: parity is an invariant.

Two litres are possible because 2 = 6 − 4:

(0,0) → (0,6) → (4,2) → (0,2)

The states are ordered as (4-litre jug, 6-litre jug): fill the 6, pour into the 4 until it is full, then empty the 4. Two litres remain in the 6, and the other jug is empty.

8. More verified cases

Jugs 3–5, target 4

The certificate is 4 = 2 · 5 − 2 · 3. With states ordered as (3,5):

(0,0) → (0,5) → (3,2) → (0,2)
      → (2,0) → (2,5) → (3,4) → (0,4)

Each pour continues until its source is empty or its destination is full; the final state holds 4 litres in the 5-litre jug.

Jugs 2–7, target 1

Here 1 = 7 − 3 · 2. With states ordered as (2,7):

(0,0) → (0,7) → (2,5) → (0,5)
      → (2,3) → (0,3) → (2,1) → (0,1)

Repeated 2-litre portions are subtracted from the 7-litre jug.

Jugs 6–10, target 8

GCD(6,10)=2 divides 8. One certificate is 8 = 3 · 6 − 10; the following route realizes the same volume with another balance, 8 = 2 · 10 − 2 · 6. States are ordered as (6,10):

(0,0) → (0,10) → (6,4) → (0,4)
      → (4,0) → (4,10) → (6,8) → (0,8)

Jugs 6–9, target 4

It is impossible: GCD(6,9)=3 does not divide 4. Every reachable volume is a multiple of 3.

9. The closed 8–5–3 variant

Another classic uses three vessels of 8, 5, and 3 litres. This time the assumptions change: the 8-litre vessel starts full, there is no source or drain, and only complete pours are allowed, stopping when the source is empty or the destination is full. The task is to split the 8 litres into two equal portions of 4.

Writing states in the order (8,5,3), one solution 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: conservation of water is the dominant invariant here. We cannot apply the two-jug source-and-drain criterion without changes; there are three capacities, a closed system, and a partition goal. The assumptions must be stated before using a theorem.

10. Shortest-path search and final checks

A Bézout certificate verifies arithmetic compatibility, but it does not replace the capacity check or guarantee that its coefficients translate directly into the shortest route. To find that route, build the directed state graph: every state is a vertex and every legal move is a directed transition. With two jugs there are at most (a+1)(b+1) pairs, so breadth-first search, or BFS, always terminates.

queue ← [(0,0)]
visited ← {(0,0)}

while queue is not empty:
    state ← remove first
    if state is (d,0) or (0,d): reconstruct path
    generate: fill A, fill B, empty A, empty B,
              pour A→B, pour B→A
    for each generated state not in visited:
        add it to visited
        enqueue it and store its predecessor

BFS visits routes with fewer transitions first: the first route that reaches the goal uses the minimum number of moves under the stated rules. For the closed 8–5–3 system, the initial state, number of coordinates, goal test, and generator all change: start at (8,0,0), seek (4,4,0), and generate only pours between every pair of containers.

Verification checklist

1. State the coordinate order and check capacity bounds in every state.
2. Check that every pour ends with an empty source or a full destination.
3. Compute the GCD and verify that it divides the target.
4. Check d ≤ max(a,b) in the open model with a one-jug target.
5. Do not confuse negative coefficients with negative water.
6. Do not confuse a Bézout certificate with the move sequence.
7. If ax+by=d is the final balance, verify that the other jug is empty.
8. If the source, drain, or number of vessels changes, redefine the state space.

Three quick checks

• With 6 and 10 litres, measuring 5 is impossible because 2 does not divide 5.
• With 3 and 5 litres, 7 is an integer combination, but it cannot fit in one jug: the capacity bound fails.
• With 4 and 6 litres, measuring 2 is possible, and the displayed route really ends with the other jug empty.

The water-jug problem separates the roles of several mathematical tools beautifully: the invariant prevents fruitless searches, Bézout certifies arithmetic compatibility, and the state graph, together with the physical constraints, turns that certificate into a concrete, verifiable, and optimizable procedure.

---

Edited by Salvatore Mosaico.