Die Hard: With a Vengeance - 3 and 5 gallon jugs

This old problem is particularly well-known from the film “Die Hard: With a Vengeance”. 

You have a 5 gallon jug and a 3 gallon jug and need to measure out exactly 4 gallons.  How can you do it?

In the film they have a time limit and a reason for getting it right (a bomb will go off if they aren’t accurate).

If you haven’t seen the problem before then please do work on it before looking for the answer. 

There are lots of webpages that give the solution to the problem (Google is your friend), and the answer is also given in the film itself.  It also appears near the bottom of the trivia page about the film.  

There are a couple of interesting things about this problem that I haven’t seen noted elsewhere.

1]  It is great that a Hollywood movie uses problems like this and bring them to a wider audience.

2]  The problem itself needs to be stated more carefully than it appears above: for example the jugs need not be uniform in cross-section (so you can’t just fill both to half-way and then combine) and there are no markings on the jugs (you can’t just read off the “4 gallon line”).

3]  Real life issues need to be ignored (the 3 gallon jug does hold exactly 3 gallons, and these jugs can be poured from without any water spilling - I can’t get a measuring jug to do this!).

Mathematising the problem

Many webpages give the answer as a list of things to do.  Sometimes it is noted that there are two solutions to the problem (although there are clearly lots of solutions - you could just pour water from one jug to another for as long as you want before getting down to solving it) and sometimes the most efficient solution is sought (using the fewest number of moves).  This problem is significantly easier if it is mathematised. 

Using the first solution from the IMDB page:

1. Fill the 5 gallon jug and decant the water into the 3 gallon jug. This leaves two gallons in the big jug. 2. Empty the 3 gallon jug and pour in the two gallons from the 5 gallon jug, leaving space for one gallon in the small jug.  - this is equivalent to 5 - 3.

3. Refill the 5 gallon jug - this is equivalent to adding 5.

and pour water from it into the 3 gallon jug until the small jug's full. - Because the small jug is not used the water is essentially poured away, so this is equivalent to subtracting 3.

So: we did 5 - 3 + 5 - 3, which equals 4.

The beauty of this is that it can be generalised.  As long as we use 5s and 3s to make the answer 4, we can generate alternative answers.

3+3+3-5 = 4.  Now we just need to finish it off.  Start with 3 gallons - pour it into the big jug.  Fill the small one again and pour into the big jug.  Empty the big jug (subtract 5) pour the 1 gallon left in the small jug into the big jug and then pour a full small jug into the big jug.  In fact we are doing 3+3-5+3=4

Generalising the problem

It is also rare to see a generalisation of the problem. 

“With any two jugs, holding a and b gallons when full (where a and b are integers), can you make all of the values from 1 to a+b?”

My thoughts on this will appear in the next blog (and that is a resolution!).