Water pouring puzzle

Water pouring puzzles (also called water jug problems, decanting problems, measuring puzzles, or Die Hard with a Vengeance puzzles) are a class of puzzle involving a finite collection of water jugs of known integer capacities (in terms of a liquid measure such as liters or gallons). Initially each jug contains a known integer volume of liquid, not necessarily equal to its capacity.

Starting state of the standard puzzle; a jug filled with 8 units of water, and two empty jugs of sizes 5 and 3. The solver must pour the water so that the first and second jugs both contain 4 units, and the third is empty.

Puzzles of this type ask how many steps of pouring water from one jug to another (until either one jug becomes empty or the other becomes full) are needed to reach a goal state, specified in terms of the volume of liquid that must be present in some jug or jugs.

By Bézout's identity, such puzzles have solution if and only if the desired volume is a multiple of the greatest common divisor of all the integer volume capacities of jugs.

Rules

It is a common assumption, stated as part of these puzzles, that the jugs in the puzzle are irregularly shaped and unmarked, so that it is impossible to accurately measure any quantity of water that does not completely fill a jug. Other assumptions of these problems may include that no water can be spilled, and that each step pouring water from a source jug to a destination jug stops when either the source jug is empty or the destination jug is full, whichever happens first.

Standard example

The standard puzzle of this kind works with three jugs of capacity 8, 5 and 3 liters. These are initially filled with 8, 0 and 0 liters. In the goal state they should be filled with 4, 4 and 0 liters. The puzzle may be solved in seven steps, passing through the following sequence of states (denoted as a bracketed triple of the three volumes of water in the three jugs):

[8,0,0] → [3,5,0] → [3,2,3] → [6,2,0] → [6,0,2] → [1,5,2] → [1,4,3] → [4,4,0].

Cowley (1926) writes that this particular puzzle "dates back to mediaeval times" and notes its occurrence in Bachet's 17th-century mathematics textbook.

Reversibility of actions

Since the rules only allows stopping/turning on the boundaries of the Cartesian grid (i.e. at the full capacities of each jug), the only reversible actions (reversible in one step) are:

• Transferring water from a full jug to any jug
• Transferring water from any jug to an empty jug

The only irreversible actions that can't be reversed in one step are:

• Transferring water from a partially full jug to another partially full jug

By restricting ourselves to reversible actions only, we can construct the solution to the problem from the desired result. From the point [4,4,0], there are only two reversible actions: transferring 3 liters from the 8 liter jug to the empty 3 liter jug [1,4,3], and transferring 3 liters from the 5 liter jug to the empty 3 liter jug [4,1,3]. Therefore, there are only two solutions to this problem:

[4,4,0] ↔ [1,4,3] ↔ [1,5,2] ↔ [6,0,2] ↔ [6,2,0] ↔ [3,2,3] ↔ [3,5,0] ↔ [8,0,0]

[4,4,0] ↔ [4,1,3] ↔ [7,1,0] ↔ [7,0,1] ↔ [2,5,1] ↔ [2,3,3] ↔ [5,3,0] ↔ [5,0,3] ↔ [8,0,0]

Variant with taps and sinks

Solution to puzzle with 3 L and 5 L jugs, a tap and a drain

Two solutions on a Cartesian grid, the upper one equivalent to the diagram on the left

The rules are sometimes formulated by adding a tap (a source "jug" with infinite water) and a sink (a drain "jug" that accepts any amount of water without limit). Filling a jug to the rim from the tap or pouring the entire contents of jug into the drain each count as one step while solving the problem. This version of the puzzle was featured in a scene of the 1995 movie Die Hard with a Vengeance. This variant has an optimal solution that can be obtained using a billiard-shape barycentric plot (or a mathematical billiard).

The graph shows two ways to obtain 4 liters using 3-liter and 5-liter jugs, and a water source and sink on a Cartesian grid with diagonal lines of slope −1 (such that $x+y=const.$ on these diagonal lines, which represent pouring water from one jug to the other jug). The x and y axes represent the amounts in the 5 and 3 L jugs, respectively. Starting from (0, 0), we traverse the grid along the line segments, turning only on its boundaries, until we reach the black line denoting 4 L in the 5 L jug. Solid lines denote pouring between jugs, dashed lines denote filling a jug and dotted lines denote emptying a jug.

Concatenating either solution, traversal of the 4 L line and the reverse of the other solution returns to (0, 0), yielding a cycle graph. If and only if the jugs' volumes are co-prime, every boundary point is visited, giving an algorithm to measure any integer amount up to the sum of the volumes.

As shown in the previous section, we can construct the solution to the problem from the desired result by using reversible actions only (emptying a full jug into the sink and filling an empty jug from the tap are both reversible). To obtain 4 liters using 3-liter and 5-liter jugs, we want to reach the point (4, 0). From the point (4, 0), there are only two reversible actions: filling the empty 3-liter jug to full from the tap (4,3), or transferring 1 liter of water from the 5-liter jug to the 3-liter jug (1,3). Therefore, there are only two solutions to the problem:

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

(4, 0) ↔ (1, 3) ↔ (1, 0) ↔ (0, 1) ↔ (5, 1) ↔ (3, 3) ↔ (3, 0) ↔ (0, 3) ↔ (0, 0)

The cycle graph can be represented by the ordered pairs connected by reversible actions:

(0, 0) ↔ (5, 0) ↔ (2, 3) ↔ (2, 0) ↔ (0, 2) ↔ (5, 2) ↔ (4, 3) ↔ (4, 0) ↔ (1, 3) ↔ (1, 0) ↔ (0, 1) ↔ (5, 1) ↔ (3, 3) ↔ (3, 0) ↔ (0, 3) ↔ (0, 0)

which contains all the possible states reachable with a 3-liter jug and a 5-liter jug. The state (1, 2), for example, is impossible to reach from an initial state of (0, 0), since (1, 2) has both jugs partially full, and no reversible action is possible from this state.

Jug with initial water

Starting with 9 liters in the 12-liter jug, the solution for 5 liters is plotted in red on the left, and the solution for 4 liters is plotted in blue on the right. All the slanted lines have the same slope of -1, representing pouring water from one jug to another.

Another variant is when one of the jugs has a known volume of water to begin with; In that case, the achievable volumes are either a multiple of the greatest common divisor between the two containers away from the existing known volume, or from zero. For example, if one jug that holds 8 liters is empty and the other jug that hold 12 liters has 9 liters of water in it to begin with, then with a source (tap) and a drain (sink), these two jugs can measure volumes of 9 liters, 5 liters, 1 liter, as well as 12 liters, 8 liters, 4 liters and 0 liters. The simplest solution for 5 liters is (9,0) → (9,8) → (12,5); The simplest solution for 4 liters is (9,0) → (12,0) → (4,8). These solutions can be visualized by red and blue arrows in a Cartesian grid with diagonal lines (of slope -1 such that $x+y=const.$ on these diagonal lines) spaced 4 liters apart, both horizontally and vertically.

Again, if we restrict ourselves to reversible actions only, from the desired point (5,0), there are only two reversible actions: transferring 5 liter of water from the 12-liter jug to the 8-liter jug (0,5), or filling the empty 8 liter jug to full from the tap (5,8). Therefore, there are only two solutions to the problem:

(5, 0) ↔ (0, 5) ↔ (12, 5) ↔ (9, 8) ↔ (9, 0)

(5, 0) ↔ (5, 8) ↔ (12, 1) ↔ (0, 1) ↔ (1, 0) ↔ (1, 8) ↔ (9, 0)

For the 4 liter question, since $4\equiv 0\!\mod \!4$, one irreversible action is necessary at the start of the solution; It could be simply pouring the whole 9 liters of water from the 12-liter jug to the sink (0,0), or fully fill it to 12 liters from the tap (12,0). Then, we can construct our solutions backwards as before:

(4, 0) ↔ (4, 8) ↔ (12, 0) ← (9, 0)

(4, 0) ↔ (0, 4) ↔ (12, 4) ↔ (8, 8) ↔ (8, 0) ↔ (0, 8) ↔ (0, 0) ← (9, 0)

Solution for three jugs using a barycentric plot

Two solutions to the standard puzzle using a barycentric plot

If the number of jugs is three, the filling status after each step can be described in a diagram of barycentric coordinates, because the sum of all three integers stays the same throughout all steps. In consequence the steps can be visualized as billiard moves in the (clipped) coordinate system on a triangular lattice.

The barycentric plot on the right gives two solutions to the 8, 5 and 3 L puzzle. The yellow area denotes combinations achievable with the jugs. Starting at the square, solid red and dashed blue paths show pourable transitions. When a vertex lands on the dotted black triangle, 4 L has been measured. Another pour to the diamond yields 4 L in each 8 and 5 L jugs.

The blue path is one step shorter than the path for the two-jug puzzle with tap and drain, as we can accumulate 4 L in the 8 L jug, absent in the two-jug variant.

See also

• Rope-burning puzzle, another class of puzzles involving the combination of measurements
• Einstellung effect

Literature

• Cowley, Elizabeth B. (1926). "Note on a Linear Diophantine Equation". Questions and Discussions. American Mathematical Monthly. 33 (7): 379–381. doi:10.2307/2298647. JSTOR 2298647. MR 1520987.
• Tweedie, M. C. K. (1939). "A graphical method of solving Tartaglian measuring puzzles". The Mathematical Gazette. Vol. 23, no. 255. pp. 278–282. JSTOR 3606420.
• Saksena, J. P. (1968). "Stochastic optimal routing". Unternehmensforschung. 12 (1): 173–177. doi:10.1007/BF01918326. S2CID 10064660.
• Atwood, Michael E.; Polson, Peter G. (1976). "A process model for water jug problems". Cognitive Psychology. 8 (2): 191–216. doi:10.1016/0010-0285(76)90023-2. S2CID 54388726.
• Rem, Martin; Choo, Young il (1982). "A fixed-space program of linear output complexity for the problem of the three vessels". Science of Computer Programming. 2 (2): 133–141. doi:10.1016/0167-6423(82)90011-9.
• Thomas, Glanffrwd P. (1995). "The water jugs problem: solutions from artificial intelligence and mathematical viewpoints". Mathematics in School. Vol. 24, no. 2. pp. 34–37. JSTOR 30215221.
• Murray-Lasso, M. A. (2003). "Math puzzles, powerful ideas, algorithms and computers in teaching problem-solving". Journal of Applied Research and Technology. Vol. 1, no. 3. pp. 215–234.
• Lalchev, Zdravko Voutov; Varbanova, Margarita Genova; Voutova, Irirna Zdravkova (2009). "Perlman's geometric method of solving liquid pouring problems".
• Goetschalckx, Marc (2011). "Single Flow Routing Through a Network". Supply Chain Engineering. International Series in Operations Research & Management Science. Vol. 161. pp. 155–180. doi:10.1007/978-1-4419-6512-7_6. ISBN 978-1-4419-6511-0.