The Three Canteens

Date: 09/18/97 at 10:40:26
From: Joe
Subject: The Three Canteens

Two men wandering in the desert come upon a trail. In hopes of finding 
help sooner, they decide to split up, each taking half their remaining 
water, and set off in opposite directions along the trail.

They have only one 14-cup canteen full of water, and two empty 
canteens that will hold nine and five cups respectively. The only way 
for them to measure water is by pouring water from one canteen to 
another until the first is empty or the second is full. How can they 
measure seven cups into each of the two larger canteens?

Please send me a solution with the least number of "pourings."

Date: 09/18/97 at 13:21:40
From: Doctor Rob
Subject: Re: The Three Canteens

At each step you have either:

  (1) just emptied a canteen, so all you can do is pour either of the
      other two into it, or pour either of the other two into each 
      other; or

  (2) just filled a canteen, so all you can do is pour from it into
      either of the other two, or pour either of the other two into 
      each other.

In either case, there are at most four possibilities. You can draw a
diagram with dots representing the contents of the three canteens and
arrows indicating that you can get from one state to another by 
filling or emptying a canteen into another.  

The initial state is 14-0-0; there are only two possible next states: 
9-0-5 (fill the small canteen) or 5-9-0 (fill the medium canteen. 
From the former state, you can get to 14-0-0 (empty the small canteen 
into the big one), 9-5-0 (empty the small canteen into the middle 
one), or 0-9-5 (empty the large canteen into the middle one). 

From 5-9-0 you can get to 14-0-0 (empty the middle canteen into the 
large one), 0-9-5 (empty the large canteen into the small one), or 
5-4-5 (fill the small canteen from the middle one). This part of the 
diagram looks like this:

                          O 14-0-0
                         ^ ^
                        /   \
                  14->9/     \14->5
                      /       \
                     v         v
                    O 5-9-0     O 9-0-5
                   ^ ^         ^ ^
                  /   \       /   \
             9->5/     \     /     \5->9
                /  14->5\   /14->9  \
               v         v v         v
        5-4-5 O --------> O 0-9-5     O 9-5-0
             / \  5->9               / \
            /   \                   /   \

As you draw the diagram, you will discover that two of the arrows 
leading out of any dot will lead to two of the four dots labeled 
14-0-0, 9-0-5, 5-9-0, and 0-9-5. These you can ignore, since they lead 
back to the beginning of the diagram. Furthermore, another arrow will 
lead back up to a dot just visited (making a two-headed arrow), which 
can also be ignored. That leaves just one arrow leading to a new dot.

There are two short paths in this diagram that lead from 14-0-0 to 
7-7-0. One passes through 5-4-5, and the other through 9-5-0. I leave 
it to you to find the single pourings which lead out of each of these 
two dots to new, not-yet-visited dots. 

Then from each of these, there is a single pouring leading to a new 
dot, and so on. Eventually each will lead to 7-7-0. One is shorter 
than the other, and that is your answer.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/