Associated Topics || Dr. Math Home || Search Dr. Math

### 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

-Doctor Rob,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search