Liquid water pouring puzzles

Water pouring puzzles (also called water jug problems 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.

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 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. This same puzzle was featured in a scene of the movie Die Hard with a Vengeance.

Variant with taps and sinks

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 variant of the problem can be rephrased as a problem where the tap and sink are replaced by a single additional jug which has the capacity equal to the sum of the capacities of the other jugs and an initial amount of liquid equal to the sum of the initial amount of air in the other jugs. So the 2 jugs problems with tap and sink become equivalent to 3 jugs problems.

Three jugs

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 some kind of billard moves in the (clipped) coordinate system on a triangular lattice.

Literature

References

    This article is issued from Wikipedia - version of the Thursday, December 17, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.