A Different Look at an Old Puzzle

Reading through a paper on Public Key Cryptography (yeah, I know how to live), by Shai Simonson of Stonehill College, I was reintroduced to an old problem from my youth. "In the 1995 movie Die Hard: With a Vengeance (aka Die Hard III), Bruce Willis and Samuel L.Jackson play a bomber's deadly game as they race around New York trying to prevent explosions.In order to stop one explosion, they need to solve the following puzzle:

Provided with an unlimited water supply, a 5-gallon jug, and a 3-gallon jug, measure outprecisely 4 gallons, by filling and emptying the jugs." If you have never tried this problem, you might pull out the pencil and paper and have a go before you read on.

In a graph theory variant of this problem, the unlimited supply is often replaced with an eight gallon jug, but the problems are equivalent. I had just hours before read the same problem in reviewing Nets, Puzzles, and Postmen by Peter M. Higgins.

Simonson goes on to describe a little history of the problem, "Of course this puzzle was not invented for this movie. Most references attribute the puzzle and its variations to Tartaglia [Tweedie, M.C.K., A Graphical method of Solving Tartaglian Measuring Puzzles, Mathematical Gazette, 23, (1939) 278-282.], but the earliest known version of the problem occurs in the "Annales Stadenses" compiled by Abbot Albert of the convent of the Blessed Virgin Mary in Stade. Stade is a small city on the west side of the Elbe estuary a bit downriver from Hamburg. The date of compilation is uncertain, but seems to be 1240."

"The puzzle is also discussed in detail at the wonderful educational mathematics site cut the knot created by Alex Bogolmony ".

Knowing you would be interested, I copied a short clip from Bogolmony's site where he retells the story of how, “Siméon Denis Poisson (1781-1840) was a famous French mathematician of the last century. He worked in celestial mechanics, probability, calculus, electricity and magnetism. He is known to be designated for a medical carreer by his family. Edward Kasner and James Newman Mathematics and the Imagination refer to Poisson's biographer, Arago:
“Siméon Poisson's family tried to make him everything from a surgeon to a lawyer, the last on the theory that he was fit for nothing better. One or two of these professions he tackled with singular ineptitude, but at last he found his métier. It was on a journey that someone posed to him a problem similar to the one below (above on this page - AB). Solving it immediately, he realized his true calling and thereafter devoted himself to mathematics, becoming one of the greatest mathematicians of the nineteenth century." ahhhh now you wonder how many young people discovered their love for mathematics in a darkened theater as they shouted out help to Willis and Jackson, "No, Fill the three and dump it into the five!".

The graphic NET for the problem is in the photo at the top. Imagine the points x,y as giving the amount in each of the two jugs. The x-coordinate shows how much is in the five-gallon jug and the y-coordinate shows how much is in the three-gallon jug. Each of the paths on the graph shows a possible move. For instance, if we start at (0,0) nothing in the two jugs, there are two paths we may follow, rigth out the x-axis to the point (5,0), or vertically up the y-axis to (0,3). The object is to end up at (4,0) or (4,1) or (4,2) or (4,3) since each of these will have a jug containing four gallons. To solve it, just move along the lines from point to point and if you get stuck, go back a point and take a different path. In the language of the graph-theory people, this is called a breadth first search (I think).

Have fun, but keep in mind you may be learning important math along the way. Simonson points out the reason for his including the puzzle in his work, "This puzzle is useful for studying public-key cryptography, because the solution embodies the two major related number-theoretic results: Euclid’s algorithm [I just realized I have never written up anything on this, perhaps because so much has been done so well in other places, like this page ] and Fermat’s Little Theorem.

I found a post by David Singmaster, one of the foremost experts on Recreational Mathematics, who provides some additional history of the problem, and an incentive for young mathematicians (see the bold below)...
" Measuring With Jugs.... I have reorganised the notation of these problems. Tweedie, MG 23 (1939) 278-282, is the source of the triangular graphical method of solution. Halving 8 using 5 and 3 is in Abbot Albert which seems to be the earliest version. Pacioli, De Viribus,
seems to be the first to use any other values, e.g. halving 12 using 7 and 5. Tartaglia seems to be the first to divide in thirds, e.g. divide 24 in thirds using 5, 11, 13. The general problem of what can be obtained from a, b, c with c full to start seems to be first treated by A. Labosne is his 5th ed. of Bachet's Problemes and appears to still be unsolved when c < a+b." So have a go children!!!