The Die Hard 3 Problem ...

diehard3.jpg diehard-f.jpg

In the movie Die Hard 3, our heros, John McClain (Bruce Willis) and Zeus (Samuel L. Jackson), are at the bidding of the evil Peter Krieg (Jeremy Irons). First they are sent to the pay phone, then to the subway, and finally to the park. It is here that they must make exactly four gallons from five and three gallon jugs. They did it just in time.

diehard-c.jpg diehard-d.jpg

How did they do it? The steps are simple, once you see them.

dh1.jpg

(1) Fill the five gallon jug. Three gallon jug is empty.

(2) Empty three gallons from the five gallon jug into the three gallon jug.

(3) There remains two gallons in the five gallon jug. Empty the three gallon jug.

(4) Pour the two gallons into the three gallon jug.

(5) Fill the five gallon jug and pour one gallon from it into the three gallon jug - filling the three gallon jug.

(6) Four gallons remain in the five gallon jug. We have solved the problem.

Problem. Given and 11 gallon and a 4 gallon jug. Make exactly one gallons.

MATHCan you follow these steps?

MATH

Thus we have exactly one gallon. Also, we can obtain $11-3=8$ gallons. Along the way we have made every number of gallons, from one to eleven.

There a much quicker way to get the eight gallons? What is it?

The mathematical solution.

There is a very general way to solve this problem. For it we suppose that there are two jugs of $p$ $<$ $q$ gallons respectively. Suppose also that $p$ and $q$ are relatively prime. Note that two numbers are called relatively prime if their greatest common divisor is $1.\ \ $Then, for any integer $k<q$ there are integers $m$ and $n$ such that MATHThis is a theorem from the subject of number theory. While we won't prove it here, we do need to interpret it in the context of our problem. If $m$ or $n$ is negative this means we are emptying a jug of $p$ or $q$ gallons respectively. Similarly if $m$ or $n$ is positive this means we are filling a jug of $p$ or $q$ gallons respectively. For example, suppose $p=3 $ and $q=5.$ Then with $k=4,$ it is easy to see that MATHSo, we can solve the $3,5$ jug problem to make four gallons by filling the three gallon jug three times and emptying the five gallon jug once. Can you construct the solution. Similarly, MATH In this case, there is a solution obtained by filling the five gallon jug twice and emptying the three gallon jug twice. (Solution. Fill the five gallon jug and empty three gallons to the three gallon jug. Empty the three gallon jug. Now empty the remaining two gallons from the five gallon jug. Next refill the five gallon jug and empty one gallon from it into the three gallon jug. This gives four gallons. Now empty the three gallon jug.)

This highlights the problem and shows that we must have jugs with relatively prime capacity to accomplish the task. You can see that if $p$ and $q$ are not relatively prime, then any such combination $mp+nq$ will have the divisor given by the greatest common divisor. (It could have other divisors, as well.

We now have an application of a theorem of abstract number theory to a practical problem of capacity and achieving a certain volumetric measure. This is higher mathematics at work.

We could also apply this to length measurement.

Example

Suppose that you have sticks of exactly five meters and seven meters in length. Then it is possible to make any integer-meter measurment.

Solution

How? Use the result above to make any measurement up to six meters. Then add the seven meter stick to get any integer length up to 13 meters. Add the seven meter stick again to get any integer length up to 21 meters, and so on.




Problems:

  1. Given a 7 gallon and a 3 gallon jug, obtain exactly 5 gallons.

  2. Suppose you have two jugs of $p$ and $q$ gallons respectively. Show that you can obtain any number of gallons between $1$ and $p$ if $p$ and $q$ are relatively prime*. (Hint. In this problem, you cannot try to solve for something directly; you must instead explore what can happen. Try a few examples such as the 7 and 3 gallon jug problem above. This will lead to a general procedure.)

  3. Given an $9$ minute egg timer and a $5$ minute egg timer. Show how to boil a $13$ minute egg. Show how to boil an egg for any number of minutes. (Hint. This problem is very much like the Die Hard problem.

  4. Join the following array with exactly 4 straight lines without lifting your pencil and without tracing over a segment already drawn.MATH Show me the solution.

  5. What is the next number in the sequence, which appeared in the New York Times: 2, 3, 3, 5, 10, 13, 39, 43, 172, 177, ...

  6. What is the next number in the sequence, 1, 1, 2, 3, 5, 8, ...

  7. Can you figure out how to plant 7 rosebushes so that they form 6 different straight lines with 3 rosebushes in each line?

*Two numbers are called relatively prime if their greatest common divisor is $1.$