Jug Problem: Make 1 from 5 and 7

Given:

• a five gallon jug
• a seven gallon jug
• a way to fill up the jugs
• a way to pour out water

End up with:

• exactly 1 gallon of water in one of the jugs.

This is a variation on the Die Hard 3 problem (make 4 from 3 and 5). (movie)

Solution:

	water	space	water	space
start with both jugs empty	0	5	0	7
fill the 7	0	5	7	0
pour 7 into 5	5	0	2	5
empty the 5	0	5	2	5
pour 7 into 5	2	3	0	7
fill the 7	2	3	7	0
pour 7 into 5	5	0	4	3
empty the 5	0	5	4	3
pour 7 into 5	4	1	0	7
fill the 7	4	1	7	0
pour 7 into 5	5	0	6	1
empty the 5	0	5	6	1
pour 7 into 5 (done)	5	0	1	6
empty the 5 (just to be tidy)	0	5	1	6

So, what have we done overall? We've filled the 7 gallon jug three times, and emptied the 5 gallon jug four times. Each time we filled the 7 gallon jug, it started out empty. Each time we emptied the 5 gallon jug, we emptied it at a time that it was full.

That can be expressed as: (7⋅3) + (5⋅(-4)) = 21 - 20 = 1

But notice: along the way, at various times we also had 2, 4 and 6 in the seven gallon jug. That is, we had every integer amount between 1 and 7, except 3. How can we make 3?

Can we figure it out from the math? That is, can we find integers a and b such that 7a + 5b = 3?

If we solve the equation for b, we get:

b = (3 -7a)/5

Since m and n both have to be integers, we can just try some different integers for a until we get a result for b that is also an integer. That is, we need (3-7a) to be divisible by 5:

Bingo! So, if b is -5, and a is 4, then we have our answer: 7(4) + 5(-5) = 3

So, this would suggest that if we just continue the process we used to get 1 gallon just one more step, we can get three gallons:

So we repeat the last two lines of the table above:

	water	space	water	space
start with both jugs empty	0	5	0	7
⋮ many steps omitted here (see table above) here next are the last two lines of the previous table:
pour 7 into 5	5	0	1	6
empty the 5	0	5	1	6
and we continue from here:
pour 7 into 5	1	4	0	7
fill the 7	1	4	7	0
pour 7 into 5 (done)	5	0	3	7
empty the 5 (just to be tidy)	0	5	3	7

Now, the real reason for emptying the five at the end should become more clear—it makes the math work out. We can use the equation ap + bq = x, where:

• p and q are the sizes of the jugs
• x is the amount of water we are looking for
• a and b represent how many times we fill up or empty the jugs

But will it always work out? Can we always find a solution? That is a mystery for our next lesson.

If you want a hint, this web page may help:
http://supremeedible.blogspot.com/2007/09/pack-my-box-with-five-dozen-liquor-jugs.html

P. Conrad, 04/14/2008