Water pouring puzzle

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Starting state of the standard puzzle

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

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[edit]

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[edit]

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 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.

Variant with taps and sinks[edit]

The solution to the puzzle, using two containers, a tap and a drain

The rules are sometimes formulated by adding a source (tap) and a drain (sink) which provide an infinite amount of additional water and an opportunity to pour all liquid from any jug into the sink. 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 is identical to the original, as a third container capable of holding the contents of the first two is mathematically equivalent to a tap or drain capable of filling or emptying both containers. An optimal solution can be easily obtained using a biliard-shape barycentric plot (or a mathematical billiard).[5]

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 are visualized by red and blue arrows in the Cartesian plot below:

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.

Three jugs[edit]

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.[7] In consequence the steps can be visualized as some kind of billard 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.

Literature[edit]

  • 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.CS1 maint: ref=harv (link)
  • Tweedie, M. C. K. (1939). "A graphical method of solving Tartaglian measuring puzzles". Math. Gaz. 23 (255). pp. 278–282. JSTOR 3606420.
  • Saksena, J. P. (1968). "Stochastic optimal routing". Unternehmensforschung. 12 (1). pp. 173–177. doi:10.1007/BF01918326.
  • Atwood, Michael E.; Polson, Peter G. (1976). "A process model for water jug problems". Cogn. Psychol. 8. pp. 191–216. doi:10.1016/0010-0285(76)90023-2.
  • Rem, Martin; Choo, Young il (1982). "A fixed-space program of linear output complexity for the problem of the three vessels". Sci. Comput. Program. 2 (2). pp. 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". Math. School. 24 (2). pp. 34–37. JSTOR 30215221.
  • Murray-Lasso, M. A. (2003). "Math puzzles, powerful ideas, algorithms and computers in teaching problem-solving". J. Res. Techn. 1 (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". Intl. Ser. Operat. Res. & Manag. 161. pp. 155–180. doi:10.1007/978-1-4419-6512-7_6.

References[edit]

  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.
  7. ^ Weisstein, Eric W. "Three Jug Problem". mathworld.wolfram.com. Retrieved 27 August 2019.