Measuring with Jugs

Given a 5-liter jug, a 3-liter jug, and an unlimited supply of water, how do you measure out exactly 4 liters?

In her book In Code: A Mathematical Journey, Sarah Flannery gives this classic brainteaser as an example of the sorts of playful puzzles that her father, a mathematics lecturer at the Cork Institute of Technology in Ireland, often offered to her and her four younger brothers at dinnertime and other occasions. “My dad gave it to me when I was quite young, probably about 5 years old,” she recounts.

Now a student at Cambridge University, Flannery achieved fame in 1999 when she was named Ireland’s Young Scientist of the Year at the age of 16 for her discoveries involving cryptography.

The jugs problem and its variants have been around since the 13th century. It even made a guest appearance in the 1995 movie Die Hard with a Vengeance, in which characters played by Bruce Willis and Samuel L. Jackson had to solve the puzzle in 30 seconds or so on the way to defusing a bomb.

Here’s one way to do the original puzzle. Fill the 5-liter jug. Empty 3 liters from the 5-liter jug into the 3-liter jug, leaving 2 liters. Empty the 3-liter jug. Pour the 2 liters from the 5-liter jug into the 3-liter jug. Fill the 5-liter jug and pour 1 liter from it into the 3-liter jug, filling it. That leaves 4 liters in the 5-liter jug. Problem solved.

Flannery’s father liked to make the most of a simple puzzle by extending it whenever possible. Can you measure out exactly 1 liter? What if you started with 9- and 4-liter jugs? In that case, can you get every measure from 1 to 13 liters? What’s the most efficient way of doing any of these measurements?

“This is perhaps what makes the puzzles so worthwhile: some have the germs of greater things in them,” Flannery writes. “When presented to enthusiastic children hungry for challenges, these puzzles can teach a lot about logical thinking, while providing amusement.”

The “measuring with jugs” problem has become a staple of computer-science courses, and students are sometimes asked to develop an algorithm to solve the general problem: Given an infinite supply of water and two jugs holding exactly B and S liters (where B is greater than S), show how to get exactly P liters (where P is less than or equal to B) in one of the jugs. The problem can be generalized further to n jugs.

Thomas J. Pfaff of Ithaca College and Max M. Tran of Columbus, Ohio, offer a solution to the generalized two-jug problem in the current issue of the Journal of Recreational Mathematics. They prove that if B and S are relatively prime, any integer amount of water between 1 and B + S can be obtained. Two integers are relatively prime if they share no divisors other than 1. For example, 12 has the divisors 1, 2, 3, 4, 6, and 12, and 13 has the divisors 1 and 13. Hence, 12 and 13 are relatively prime. On the other hand, 14 shares with 12 the divisor 2, so 12 and 14 are not relatively prime.

So it’s possible, for instance, to use 5- and 12-liter jugs to obtain any integer amount of water from 1 to 17 liters.

Here’s an example of how Pfaff and Tran’s algorithm works when using 5- and 12-liter jugs. To obtain amounts of water between 1 liter and 4 liters, begin by putting 10 liters of water into the 12-liter jug. Fill the 5-liter jug and top off the 12-liter jug, leaving 3 liters. Empty the 12-liter jug and pour into it the 3 liters of water in the 5-liter jug. Add 5 more liters to the 12-liter jug, leaving 4 liters of empty space. Fill the 5-liter jug and top off the 12-liter jug, leaving 1 liter in the 5-liter jug.

“If we continue in this fashion, we claim that we will cycle through all the values between 1 and 4,” Pfaff and Tran write.

A graphical method for solving such jug problems was introduced by M.C.K. Tweedie in a 1939 paper.

Paolo Boldi, Massimo Santini, and Sebastiano Vigna of the Università degli Studi di Milano in Italy provide a detailed analysis of the n-jug problem in the June 2002 issue of Theoretical Computer Science.

Without such general frameworks, these puzzles can be troublesome. “Tell me how to measure exactly 4 liters with only a 6-liter and a 3-liter jug,” Flannery’s father might ask in extending the original jugs puzzle. Of course, it can’t be done.

Flannery writes, “This variation on a theme lets you learn the very valuable lesson that sometimes problems may not have solutions of the type you seek (and that you cannot trust even your father to give you solvable puzzles).”