The Water Jugs
Solution

Puzzle 1: Yes, the water can be divided into two equal portions:

        ( 8, 0, 0 )    0: Beginning
        ( 3, 5, 0 )    1: 5 gallons from #1 into #2.
        ( 3, 2, 3 )    2: 3 gallons from #2 into #3.
        ( 6, 2, 0 )    3: 3 gallons from #3 into #1.
        ( 6, 0, 2 )    4: 2 gallons from #2 into #3.
        ( 1, 5, 2 )    5: 5 gallons from #1 into #2.
        ( 1, 4, 3 )    6: 1 gallon from #2 into #3.
        ( 4, 4, 0 )    7: 3 gallons from #3 into #1.  DONE!
      

Puzzle 2: It is impossible to divide the water into portions of 4, 2 and 2 gallons. To see why, consider the following diagram of the 24 possible arrangements of the water in the jugs:

        800
        701  710
        602  611  620
        503  512  521  530
        ...  413  422  431  440
        ...  ...  323  332  341  350
        ...  ...  ...  233  242  251  
        ...  ...  ...  ...  143  152 
        ...  ...  ...  ...  ...  053
      

The rules for pouring actually define a directed graph or "digraph" that points from one arrangement to the others that can be reached from it. Starting from the arrangement 800, we can find all new arrangements reachable in one pouring. Now we can look at all new arrangements reachable from those arrangements, and so on. This is a "breadth first" search of the digraph. The results are:

        800  
        350  503             1 Pouring
        053  323  530        2 Pourings
        620  233             3 Pourings
        602  251             4 Pourings
        152  701             5 Pourings
        143  710             6 Pourings
        440  413             7 Pourings
        (no more arrangements are reachable)
      

From this list, we see that:

• It takes seven pourings to get from 800 to 440, and there can be no shorter solution.
• There is no way to divide the water into portions of 4, 2, and 2 gallons, since the arrangements 422 and 242 are not reachable from 800.

Using this methodical and exhaustive method of looking at the problem, it should be easy to set up and solve similar problems, determining whether there is a way of reaching the desired arrangement, the shortest number of steps, and the actual sequence of steps.

On the other hand, you should have been able to say, almost immediately, that the 422 solution is impossible. Why? How did the third jug end up with just 2 gallons? If it's full or empty, that's easy, but if it's partially full, that can only happen because:

• The entire contents of another jug were poured in, or
• The contents of jug 3 were poured into another jug until it was filled.

        800
        701  710
        602  xxx  620
        503  xxx  xxx  530
        ...  413  xxx  xxx  440
        ...  ...  323  xxx  xxx  350
        ...  ...  ...  233  xxx  251 
        ...  ...  ...  ...  143  152
        ...  ...  ...  ...  ...  053
      

Puzzle 3: spring for the 11 gallon jug!

Fact 1: if you have two jugs of integral sizes p and q, and if p and q are relatively prime, then you can measure out every integral amount from 0 to p+q, and nothing else.

Fact 2: if the greatest common factor of p and q is r, then you can measure out every integral multiple of r from 0 to p+q, and nothing else.

Conclusion: choosing the 11 gallon jug maximizes p+q. Since 11 and 12 are relatively prime, no smaller jug size will yield a greater number of measurable amounts of water. Thus, your thoughtful gift of an 11 gallon jug will allow Crusoe to measure out the 24 different integral gallon sizes from 0 to 23 gallons.

Reference:

1. Richard Bellman, Kenneth Cooke, Jo Ann Lockett,
   Algorithms, Graphs, and Computers,
   Chapter 5: "Juggling Jugs",
   Academic Press, 1970

Back to The Water Jug Puzzle.