# Die Hard III

Here is the water measuring puzzle depicted in Die Hard III. The puzzle has endless variations (see below).

## Puzzle

Bruce and Sam find themselves by a fountain with only two empty water bottles - one can hold exactly 3 gallons, the other exactly 5 gallons. There are no markings of any kind on the bottles. They know that they must somehow measure exactly 4 gallons of water, else catastrophe strikes. How can they accomplish their task?

## Variations

Besides easily changing the background story, the puzzle can be modified by using different sized containers. It is possible to measure any number of gallons (up to the size of the larger container) as long as the sizes of the containers are relatively prime. In more generality, an <m>a</m>-gallon container and a <m>b</m>-gallon container can be used to measure exactly <m>c</m> gallons if and only if <m>\gcd(a,b)~|~c</m> (assuming <m>c\le \max\{a,b\}</m>).

Another option is to ask, for particular container sizes, whether it is possible to measure a particular amount of water exactly. This can be used to lead students to the conjecture about which amounts are possible for which sized containers.

## Connection to number theory

A solution to this problem can be viewed as a solution to the linear Diophantine equation <m>3x + 5y = 4</m>, where <m>x</m> and <m>y</m> are the net number of times the 3 and 5 gallon containers are filled/emptied respectively (pouring water from one container to the other results in no change).

**Hint**