The 3 Gallon 5 Gallon Problem

Photo Credit: WeGraphics

The 3 Gallon 5 Gallon Problem

My friend told me it was a famous one in a movie, though I did not know its name. Interesting as it is, I cannot see any practical use in it. Anyway, just take this artificial problem and enjoy its wise design.

The problem is as follows:

The 3-gallon 5-gallon Problem

There is a 3-gallon bucket and a 5-gallon bucket, how to gain 4-gallon water from them?

Before we see the solution, I would like to rephrase this problem.

Like the machine described in the computation theorem lectures given by Feynman, we are simulating a computer machine, although not a Turing one, with two registers: 3-gallon bucket and 5-gallon bucket. The only operations we have are: clearing the register (clear the water from bucket) and transferring data between registers (transfer water between buckets). We want to find a solution of 4 with these two registers and operations.

m and n represents the operation numbers needed for getting 4 gallon water. $p_1$ is 3 and $p_2$ is 5 here.

I can see the nearest solution sets {m,n} includes {3,-1} and {-2,2}

{3, -1} means filling in the 3-gallon bucket three times and empty the 5-gallon bucket once:

1-1

(each step consists of two squashed rectangular. Smaller one represents 3-gallon gucket and the other 5-gallon one. The number in the rectangular means its current water content. Red color indicates it is full now.)

{-2, 2} means filling in the 5-gallon bucket twice and empty the 3-gallon bucket twice:

1-1

You may easily find out that if we have the solution sets in mind, we just need to follow it strictly and design the scheme straightforward. Now I really appreciate the simple equation solutions that could provide us a basic yet efficient guideline of designing the scheme.

Is it true that we can always devise some scheme whatever the buckets size are? The answer is: as long as we can solve the equation:

(t means the final water amount we want)

Remember the famous Euclid algorithm used to compute gcd($p_1$,$p_2$) (gcd: greatest common divisor)? We can actually extend it to compute the m and n which satisfy

This very algorithm, which is called extended Euclid Algorithm (from Concrete Mathematics, Chapter 4.1, second edition) ensures we can solve the second equation.

If we let $p_1$ to be relatively prime to $p_2$, then gcd($p_1$, $p_2$) = 1. We can solve solution set {m, n} using the Euclid Algorithm Plus and multiple {m, n} with t to get {tm, tn} which satisfy:

So the key is let $ p_1 $ and $p_2$ to be prime to each other, then everything is set.