Water pouring puzzle

Last updated August 28, 2024

Water pouring puzzles (also called water jug problems, decanting problems,^[1]^[2]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.

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 Die.hard.water.puzzle.jpg — Solution to puzzle with 3 L and 5 L jugs, a tap and a drain

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 .^[4] This variant has an optimal solution that can be obtained using a billiard-shape barycentric plot (or a mathematical billiard).^[5]

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

Another variant^[6] 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

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.^[7] 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.

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.

Related Research Articles

In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is countable if there exists an injective function from it into the natural numbers; this means that each element in the set may be associated to a unique natural number, or that the elements of the set can be counted one at a time, although the counting may never finish due to an infinite number of elements.

A Pythagorean triple consists of three positive integers $a$ , $b$ , and $c$ , such that $a 2 + b 2 = c 2$ . Such a triple is commonly written $(a, b, c)$ , a well-known example is $(3, 4, 5)$ . If $(a, b, c)$ is a Pythagorean triple, then so is $(ka, kb, kc)$ for any positive integer $k$ . A triangle whose side lengths are a Pythagorean triple is a right triangle and called a Pythagorean triangle.

Peg Solitaire, Solo Noble, Solo Goli, Marble Solitaire or simply Solitaire is a board game for one player involving movement of pegs on a board with holes. Some sets use marbles in a board with indentations. The game is known as solitaire in Britain and as peg solitaire in the US where 'solitaire' is now the common name for patience.

Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize a multivariate quadratic function subject to linear constraints on the variables. Quadratic programming is a type of nonlinear programming.

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements and objective are represented by linear relationships. Linear programming is a special case of mathematical programming.

In mathematics, for given real numbers a and b, the logarithm log_b a is a number x such that b^x = a. Analogously, in any group G, powers b^k can be defined for all integers k, and the discrete logarithm log_b a is an integer k such that b^k = a. In number theory, the more commonly used term is index: we can write x = ind_ra (mod m) (read "the index of a to the base r modulo m") for r^x ≡ a (mod m) if r is a primitive root of m and gcd(a,m) = 1.

In combinatorial mathematics, two Latin squares of the same size (order) are said to be orthogonal if when superimposed the ordered paired entries in the positions are all distinct. A set of Latin squares, all of the same order, all pairs of which are orthogonal is called a set of mutually orthogonal Latin squares. This concept of orthogonality in combinatorics is strongly related to the concept of blocking in statistics, which ensures that independent variables are truly independent with no hidden confounding correlations. "Orthogonal" is thus synonymous with "independent" in that knowing one variable's value gives no further information about another variable's likely value.

In mathematics, to solve an equation is to find its solutions, which are the values that fulfill the condition stated by the equation, consisting generally of two expressions related by an equals sign. When seeking a solution, one or more variables are designated as unknowns. A solution is an assignment of values to the unknown variables that makes the equality in the equation true. In other words, a solution is a value or a collection of values such that, when substituted for the unknowns, the equation becomes an equality. A solution of an equation is often called a root of the equation, particularly but not only for polynomial equations. The set of all solutions of an equation is its solution set.

In functional programming, a monad is a structure that combines program fragments (functions) and wraps their return values in a type with additional computation. In addition to defining a wrapping monadic type, monads define two operators: one to wrap a value in the monad type, and another to compose together functions that output values of the monad type. General-purpose languages use monads to reduce boilerplate code needed for common operations. Functional languages use monads to turn complicated sequences of functions into succinct pipelines that abstract away control flow, and side-effects.

In chemistry, the amount of substance (symbol n) in a given sample of matter is defined as a ratio (n = N/N_A) between the number of elementary entities (N) and the Avogadro constant (N_A). The entities are usually molecules, atoms, ions, or ion pairs of a specified kind. The particular substance sampled may be specified using a subscript, e.g., the amount of sodium chloride (NaCl) would be denoted as n_NaCl. The unit of amount of substance in the International System of Units is the mole (symbol: mol), a base unit. Since 2019, the value of the Avogadro constant N_A is defined to be exactly 6.02214076×10²³ mol⁻¹. Sometimes, the amount of substance is referred to as the chemical amount or, informally, as the "number of moles" in a given sample of matter.

A bag-in-box or BiB is a container for the storage and transportation of liquids. It consists of a strong bladder, usually made of several layers of metallised film or other plastics, seated inside a corrugated fiberboard box.

A keg is a small cask.

In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi-Thue system, is a rewriting system over strings from a alphabet. Given a binary relation $between fixed strings over the alphabet, called rewrite rules, denoted by, an SRS extends the rewriting relation to all strings in which the left- and right-hand side of the rules appear as substrings, that is, where,,, and are strings.$

Pithos is the Greek name of a large storage container. The term in English is applied to such containers used among the civilizations that bordered the Mediterranean Sea in the Neolithic, the Bronze Age and the succeeding Iron Age. Pithoi were used for bulk storage, primarily for fluids and grains; they were comparable to the drums, barrels and casks of recent times. The name was different in other languages; for instance, the Hittites used harsi-.

Branch and cut is a method of combinatorial optimization for solving integer linear programs (ILPs), that is, linear programming (LP) problems where some or all the unknowns are restricted to integer values. Branch and cut involves running a branch and bound algorithm and using cutting planes to tighten the linear programming relaxations. Note that if cuts are only used to tighten the initial LP relaxation, the algorithm is called cut and branch.

Alligation is an old and practical method of solving arithmetic problems related to mixtures of ingredients. There are two types of alligation: alligation medial, used to find the quantity of a mixture given the quantities of its ingredients, and alligation alternate, used to find the amount of each ingredient needed to make a mixture of a given quantity. Alligation medial is merely a matter of finding a weighted mean. Alligation alternate is more complicated and involves organizing the ingredients into high and low pairs which are then traded off. Alligation alternate provides answers when an algebraic solution is not possible. Note that in this class of problem, there may be multiple feasible answers.

In logic, a functionally complete set of logical connectives or Boolean operators is one that can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well-known complete set of connectives is { AND, NOT }. Each of the singleton sets { NAND } and { NOR } is functionally complete. However, the set { AND, OR } is incomplete, due to its inability to express NOT.

In linear algebra, the Hermite normal form is an analogue of reduced echelon form for matrices over the integers Z. Just as reduced echelon form can be used to solve problems about the solution to the linear system Ax=b where x is in Rⁿ, the Hermite normal form can solve problems about the solution to the linear system Ax=b where this time x is restricted to have integer coordinates only. Other applications of the Hermite normal form include integer programming, cryptography, and abstract algebra.

The square milk jug is a variant of the one-gallon (3.785-liter) plastic milk container sold in the United States. The design was introduced in the summer of 2008 and is marketed as environmentally friendly because of the shape's advantages for shipping and storage.

A water container, water canister or water can is a medium-sized portable container for transport, storage and use of water. Large plastic bottles are sometimes called "canisters". Water canisters can for example be used for drinking water, wastewater or showering. Water canisters are used for excursions, camping, boat trips, in cabins without tap water, or as a household drinking water reserve in case of emergency.

References

↑ Weisstein, Eric W. "Three Jug Problem". mathworld.wolfram.com. Retrieved 2020-01-21.
↑ "Solving Decanting Problems by Graph Theory". Wolfram Alpha.
↑ "Decanting Problems and Dijkstra's Algorithm". Francisco Blanco-Silva. 2016-07-29. Retrieved 2020-05-25.
↑ Hint to Riddle #22: The 3 & 5 Litre Die Hard Water Puzzle. Puzzles.nigelcoldwell.co.uk. Retrieved on 2017-07-09.
↑ How not to Die Hard with Math , retrieved 2020-05-25
↑ "Choose Your Volume". brilliant.org. Retrieved 2020-09-22.
↑ Weisstein, Eric W. "Three Jug Problem". mathworld.wolfram.com. Retrieved 27 August 2019.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Weisstein, Eric W. "Three Jug Problem". mathworld.wolfram.com. Retrieved 2020-01-21.

[2] "Solving Decanting Problems by Graph Theory". Wolfram Alpha.

[3] "Decanting Problems and Dijkstra's Algorithm". Francisco Blanco-Silva. 2016-07-29. Retrieved 2020-05-25.

[4] Hint to Riddle #22: The 3 & 5 Litre Die Hard Water Puzzle. Puzzles.nigelcoldwell.co.uk. Retrieved on 2017-07-09.

[5] How not to Die Hard with Math , retrieved 2020-05-25

[6] "Choose Your Volume". brilliant.org. Retrieved 2020-09-22.

[Weisstein2019-7] Weisstein, Eric W. "Three Jug Problem". mathworld.wolfram.com. Retrieved 27 August 2019.

[1]

[2]

[3]

[4]

[5]

[6]

[7]