(A new question of the week)
A recent question about an old puzzle leads to multiple references to our archive.
Two containers
Here is the question, from a student in a non-English-speaking country:
At finals of campus-wide Brain Bowl Tournament, your team was asked to measure out exactly one gallon of water using only a 5-gallon and a 3-gallon container, without wasting any water. Your team completed the task. How did they do it?
My attempt:
I think … this is hard. I don’t know where to start, they didn’t even have initial volume of water or measurement of water so I can’t manipulate anything. But here’s my idea: fill the 3 gallon water container until it is full, then estimate where the 1/3 of the water then whoosh … I know it is wrong but at least I gave it a try.
The initial difficulty with this common puzzle is to get a clear sense of what it means. What are you starting with, and what are you allowed to do? The wording in this version leaves some facts unstated; this happens often when a problem is so well-known that an author doesn’t consider how a newcomer will read it. We have seen several variations in which the rules differ; in particular, the phrase “without wasting any water” is not usual.
Doctor Jacques answered, providing mostly just an explanation of the implied rules:
You must measure one gallon exactly: estimation is not allowed.
There are three things you can do at any stage:
- Fill one container from the tap
- Empty one container into the drain
- Pour the content of one container into the other one until either the source container is empty or the destination container is full.
Initially, the only thing you can do is (1): fill one of the containers. It turns out that either choice will lead you to the solution, although one choice is faster.
If you try to play with this, you will notice that, after the first operation, there is only one sensible thing to do at each stage, without undoing what you did in the previous stage.
I will let you experiment with these ideas, feel free to write back if you get stuck.
That last statement is one that many students miss: in order to understand an unfamiliar problem, you need to experiment with it, trying things out to get a feel for it.
In this case, the clarification and some experimentation was all that was needed:
OMG OMG!!! I’ve got an idea!! I will fill the 3-gallon container first and pour all of it in the 5-gallon container, then I will fill the 3-gallon container then pour it into the 5-gallon container until it is full, then the remaining water in the 3-gallon container is exactly one gallon!!!!! Yaaaayy!!
Would you mind if I ask the other strategy doing this problem?
This turns out to be a rather straightforward version of the puzzle, in which nothing has to be wasted and the path to the answer is fairly direct. Below, I will discuss some variants we’ve seen, and different approaches. But first, Doctor Jacques answered the student’s question, showing the other way while also demonstrating one way to organize your work:
That is correct. The other strategy would be to start with the 5-gallon container. If we call A the 5-gallon container and B the other one, the operations would be:
A B Fill A 5 0 A → B (3) 2 3 Empty B 2 0 A → B (2) 0 2 Fill A 5 2 A → B (1) 4 3 Empty B 4 0 A → B (3) 1 3 and you are left with 1 gallon in container A.
You may notice that this solution not only takes more steps; it also requires dumping a total of 6 gallons of water, which is not acceptable given the statement of the puzzle.
From the archive …
For harder versions of the puzzle, you may want more help than this student needed. We have collected some of our past discussions of questions of this type on the Selected Answers page:
Measuring with Two Containers
The most detailed of these is this one, from 2002:
4- and 9-liter Pails: How to Measure 7 Liters I have a problem that needs to be solved. I tried using cups to do this problem but without the ability to measure I just can't seem to think it out properly. Can you help? Here it is: You are trapped in a cave that has an endless supply of water. You have to create an explosive device to get out. You need to add exactly 7 liters of water to a pre-made mixture. You only have a 4-liter pail and a 9-liter pail. Neither pail has markings on it and they are not symmetrical. You do not have the use of any kind of marking device. How do you get out?
This is a considerably more difficult version (that is, it will take more steps, and therefore more thinking), but it is the more typical type, explicitly stating that there is an endless supply of water, so that we can always get more, and won’t mind “wasting” some by dumping it out. Note the additional comments that the pails are unmarked and not symmetrical (so that you can’t tip one and be sure it is exactly half full, for example). This makes it clearer what the rules are.
I started my answer by referring to two previous answers to such puzzles, and then stating, as Doctor Jacques did above, what steps are allowed. I also suggested a similar notation, making a table to keep track of what has been done:
What you want (and these pages don't give) is a strategy for solving this sort of puzzle. Let me suggest one.
One thing we need is a way to keep track of what we are doing. I like to use a chart that shows how much is in each container:
(4) (9)
--- ---
0 0
Now at each step we can either fill a pail, empty a pail, or pour from one to the other until we either empty the former or fill the latter. We can indicate on the chart what we did and what the result was:
0 9 fill (4)
4 5 pour into (4)
0 5 empty (4)
You might just draw arrows to show what happened; that's harder to do in print.
What I did here differs from Doctor Jacques’ only in the way I label the columns (using the sizes as a reminder rather than an arbitrary letter) and my use of words rather than symbols in the explanations (which was largely because of the limitations of typing text).
Next, I suggested an overall strategy. Here, I was using the puzzle as a model for general problem-solving: first we can invent a notation, then a way to think about the problem:
Now we have to figure out how to choose the steps to take. There are only a few things to do at each step, so you might just make several charts starting with different first steps, and see where each one takes you; whenever you have a choice to make, start a new chart at that point if your first choice doesn't work out.
This is an orderly search of the “state space” (the set of possible states for the pails); in other problems it might be far too time-consuming, but it is often a good way to start — this is the experimentation I referred to.
Another common strategy is to work backwards from the end of the process, as well as forward from the beginning:
It will also be helpful to know the goal. You should try working backward from the end of the chart, to see what the next to last step should look like. You want to end with 7 liters in the 9-liter pail. How could you get to that state?
0 7
You might either have poured 4 into (9):
4 3
0 7 pour into (9)
or poured 2 from (9) into (4):
2 9
4 7 pour into (4)
So you want to see if you can get amounts of 3 or 2, knowing that if you can get either of those, you can get 7. (That is, 7 = 9-2 and 7 = 3+4.)
This should make the work a lot easier. You might find it interesting to keep a list of what amounts you are able to get in either bucket, and how many steps it takes.
At this point, I left it for Cynthia to apply these ideas. I also gave a link to a page that goes much deeper into the puzzle:
2 Pails Puzzle - Cut-the-Knot, Alexander Bogomolny
This also links to a further page on the “Three Jugs Problem”. Unfortunately, these depend on Java applets, which are often not supported today.
A graphical representation
On one occasion, in 2009, I wrote up an (unarchived) explanation of a puzzle of this type based on the graphical representation of the state space that Bogomolny uses:
Bogomolny shows a way to represent the problem on a grid, which allows you to solve it almost automatically once you get used to it. For your version, you want to get 6 cups from 7 and 4, so you'd make a grid 7 by 4: 4 +---+---+---+---+---+---+---+ | | | | | | | | 3 +---+---+---+---+---+---+---+ | | | | | | | | 2 +---+---+---+---+---+---+---+ | | | | | | | | 1 +---+---+---+---+---+---+---+ | | | | | | | | 0 A---+---+---+---+---+---B---+ 0 1 2 3 4 5 6 7 Here, the horizontal coordinate represents the amount in the 7-cup container, and the vertical coordinate is the amount in the 4-cup container. We want to get from A(0,0), where both are empty, to B(6,0), where there are six cups in the larger one. If you fill a container from the source, or dump it out, you move vertically or horizontally as far as possible in the grid. If you pour from one into the other, you move at a slope of -1 to the left or right until you reach an edge of the grid. (Along such a line the sum of the amounts is constant.) You're looking for a combination of those motions that will get you from A to B. An example of a first few steps might be to follow the numbers in order as shown (on paper I'd draw all the lines showing where I've been): 4 1---+---+---+---3---+---+---+ | \ | | | | \ | | | 3 +---\---+---+---+---\---+---+ | | \ | | | | \ | | 2 +---+---\---+---+---+---\---+ | | | \ | | | | \ | 1 +---+---+---\---+---+---+---4 | | | | \ | | | | 0 A---+---+---+---2---+---B---+ 0 1 2 3 4 5 6 7 That means I filled the 4, then poured it into the 7, then filled the 4 again and poured as much as possible into the 7, leaving 1 in the 4 and the 7 full. We're awfully close, but we can't simultaneously reduce each by 1 cup; all we can do here is to empty the full one and keep going. So we continue: 4 1---7---13--+---3---9---+---+ | \ | \ | \ | | \ | \ | | 3 +---\---\---\---+---\---\---+ | | \ | \ | \ | | \ | \ | 2 11--+---\---\---\---+---\---10 | \ | | \ | \ | \ | | \ | 1 5---\---+---\---\---\---+---4 | \ | \ | | \ | \ | \ | | 0 A---6---12--+---2---8---B---+ 0 1 2 3 4 5 6 7 So we get to the goal, B, on the 14th step! Here is a shorter solution, which starts by filling the 7 rather than the 4: 4 +---+---+---2---+---+---6---+ | | | | \ | | | \ | 3 4---+---+---+---\---+---+---5 | \ | | | | \ | | | 2 +---\---+---+---+---\---+---+ | | \ | | | | \ | | 1 +---+---\---+---+---+---\---+ | | | \ | | | | \ | 0 A---+---+---3---+---+---B---1 0 1 2 3 4 5 6 7 One more step takes us to B, but since we already have 6 cups in the 7-cup container, we can say we're done after these 6 steps.
An algebraic representation
I also find another unarchived explanation by Doctor Jacques from 2008, which relates the problem to some concepts in algebra and number theory, before doing essentially what we have been doing. This time, we have 5 and 11 gallon buckets, and need to make 7:
Let A be the 11-gallon bucket and B be the 5-gallon bucket. As we have to make 7 gallons using multiples of 11 and 5, we try to find integers x and y such that: 11*x - 5*y = 7 (1) As 11 and 5 are relatively prime, this is always possible. In fact, there is a systematic way of finding x and y, based on the Extended Euclidean algorithm; however, given your age, I'm not sure you already know about it. If this is the case, you can proceed by trial and error: list the multiples of 11 until you find one that is 7 more than a multiple of 5. You will easily find the solution x = 2, y = 3, i.e.: 11*2 - 5*3 = 7 Now, if we had a third large enough container, the solution would be easy : pour 22 gallons into it (using A) and remove 15 gallons (using B). The catch is that we have no such container: everything must take place using only A and B; obviously, the 7 gallons must end up in A. Well, let us not despair, and look at what happens. As (1) shows, we must try to add 11 gallons twice, and remove 5 gallons three times; the important point is that we can do these operations in any order. We can start by filling A once (11 gallons) and removing 5 gallons twice (using B, and emptying B after each operation). This gives the following sequence: A B 11 0 fill A 6 5 pour form A to B 6 0 empty B 1 5 pour from A to B 1 0 empty B We are left with one gallon in A and nothing in B. We have added 11 once (to A) and removed 5 twice. According to (1), we still need to add 11 once and remove 5 once (indeed, 1 + 11 - 5 = 7). The problem is that we can do neither directly: we cannot add 11, because A is not empty, and we cannot remove 5, because A does not contain enough water. The trick is to combine both operations. We can pour the remaining gallon into B (without emptying B), fill A with another 11 gallons, and then pour the remaining 4 gallons into B to fill it. As B is now full, we have effectively removed 5 gallons and added 11: A B 1 0 (previous state) 0 1 pour from A to B 11 1 fill A 7 5 pour from A to B (4 gallons needed to fill B) and we are left with 7 gallons in A, as required. Note that, in total, we have indeed added 11 gallons 2 times and removed 5 gallons 3 times (although the last operation was done in two steps). Note that we used A to add and B to subtract. There is another solution, which is, in this particular case, longer. Instead of (1), we can look for a solution to: 5*x - 11*y = 7 (2) and, by trial and error (or otherwise), we find the solution x = 8, y = 3, i.e.: 5*8 - 11*3 = 7 In this case, we would use B to add and A to subtract. The first steps are: A B 0 5 fill B 5 0 pour from B to A 5 5 fill B 10 0 pour from B to A At this point, we can neither add 5 to A nor remove 11 from it. As before, we combine the operations: A B 10 5 fill B 11 4 pour from B to A (1 gallon needed to fill A) 0 4 empty A 4 0 pour from B to A and the net effect is that we have added 5 and subtracted 11. You can then repeat the process until you get 7 gallons in B. In this case, the solution is longer, but, for other capacities, this second method would be faster. Note that we don't really need to compute x and y - I did it only to show what happens. In practice, you would start by filling one container, and repeat the above operations until you get the desired result (this will always happen if the capacities are relatively prime). Note that, once you have filled one of the containers as the initial step, there is only one sensible thing to do at each subsequent step (without undoing what you already have done).
Three containers
Let’s close with an example of the three-container version, in which we don’t have an unlimited supply, and we can’t waste anything. (In effect, the third container is both our supply and our dumping place, and that is enough.) In 1997, Doctor Rob answered this question:
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."
Doctor Rob had a very different representation of the problem:
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.