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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum