Water Bucket Conundrum 
This problem has crossed my path a number of times in various guises. Perhaps you have also seen a version of it.

You are staying at a rural cabin, and the only method to get water is to draw it from a well. A 4-gallon bucket and a 9-gallon bucket are the only containers for carrying water to the cabin. In one trip to the well, what whole number amount of water in gallons could you bring back to the cabin in the buckets? No other markings are on the pails, and you can’t do any estimating—you need to supply exact whole number amounts only!

What if you had a 4-gallon bucket and a 10-gallon bucket?

What if you had an n-gallon bucket and an m-gallon bucket?

Some Ponderings:  

Recall that October’s Problem to Ponder was as follows:

You are staying at a rural cabin, and the only way that you can get water is to draw it from a well. A 4-gallon bucket and a 9-gallon bucket are the only containers that you have for carrying water to the cabin. In separate trips to the well, what whole number gallon amounts of water could you bring back to the cabin in the buckets? No other markings are on the pails, and you can’t do any estimating—you need to bring back whole number amounts only!

What if you had a 4-gallon bucket and a 10-gallon bucket?

What if you had an n-gallon bucket and an m-gallon bucket?

I have found that this problem has a lot of “reach”—it works equally well with middle school students and with college mathematics majors, and with students at all levels in between. Often, a student’s first reaction is to say that 4, 9, 13, and 0 gallons are possible, and then, when the teacher or someone else suggests that other whole numbers of gallons are possible, the student is very likely to respond, “Are you serious? How can you get anything else?” But eventually the student will realize that you can pour and make “trades” with the water from one bucket to the other. For example, filling and pouring the 4-gallon bucket into the 9-gallon bucket two times will give you 8 gallons to carry back in the 9-gallon bucket. Filling and pouring the 4-gallon bucket into the 9-gallon bucket three times will leave you with 3 gallons to carry back in the 4-gallon bucket when the 9-gallon bucket is full. In other words, all your filling and pouring yields (4 + 4 + 1) gallons in the 9-gallon bucket + 3 left over in the 4-gallon bucket.

We can get other amounts of water by pouring repeatedly from the small bucket into the larger one or from the larger one into the smaller one. For example, if we fill the 9-gallon bucket and pour it into the 4-gallon bucket, we’ll have 5 gallons of water left in the larger bucket. If we pour out the 4-gallon bucket and then fill it up again from the 5 gallons left in the large bucket, we’ll have 1 gallon remaining in the big bucket. It turns out that obtaining a 1-gallon amount is key, as you will see.

So far we have shown that it is possible to get 1, 3, 4, 5, 8, 9, and 13 gallons. See if you can figure out how to obtain the other whole number amounts that are missing. It is possible to get any whole number amount from 1 to 13 gallons with a 4-gallon and a 9-gallon bucket.

Pairing a 4-gallon bucket with a 10-gallon bucket creates a very different problem. Try as we might, with two buckets of these sizes, we can’t obtain an odd number of gallons of water to bring back from the well. In this case, repeatedly filling and pouring one bucket into the other will generate only even numbers of gallons of water. The operations that we are doing when we pour back and forth between two buckets of these sizes are either repeated addition or repeated subtraction of even numbers—and since even ± even = even, we’ll never generate an odd number of gallons of water to carry back to the cabin.

What about the general case of an m-gallon bucket and an n-gallon bucket? We’ll return with more ponderings on Water Bucket Conundrum in next month’s column.

More Ponderings: 

In the October Problem to Ponder, we first discussed some particular cases of pairs of buckets for carrying whole numbers of gallons of water from a well.

The question was, If a 4-gallon bucket and a 9-gallon bucket are your only containers for carrying water back to your cabin, what whole numbers of gallons of water  could you bring back to the cabin in one trip to the well? What if you had a 4-gallon bucket and a 10-gallon bucket?

Last month we showed that it was possible to obtain every whole number of gallons from 0 to 13 if we had only a 4-gallon and a 9-gallon bucket. We did this by making “trades” of amounts of water from one bucket into the other. For example, we could get 5 gallons by first filling the 9-gallon bucket, then pouring the water into the 4-gallon bucket until it was full, leaving us with exactly 5 gallons in the 9-gallon bucket. If we then dumped out the smaller bucket and used our remaining 5 gallons of water to fill it again, that would leave us with only 1 gallon of water in the 9-gallon bucket. We can generate all the other whole number amounts by repeatedly pouring the smaller bucket into the larger one. For example, if we fill the 4-gallon bucket 3 times, each time pouring it into the 9-gallon bucket, on the third pour we’ll have 3 gallons left in the smaller bucket when the larger one has been filled. And so forth.

However, when we tried using a 10-gallon and a 4-gallon bucket, we could obtain only even numbers of gallons of water, from 2 to 14 gallons, by making such trades. We can think of these pourings from one bucket to another as forming whole numbers from repeated additions and/or repeated subtractions of the given bucket sizes.

In general, what if you had an n-gallon bucket and an m-gallon bucket?  When is it possible to bring back all possible whole number amounts of water from 0 to (n + m)? The problem with 10 and 4 was that they had a common factor of 2. We were never able to obtain an odd number of gallons of water. What if our buckets are of size n and m, and they have a common factor of 3? Then n = 3r, and m = 3s, for some whole numbers r and s. Repeated additions or subtractions of n and m can be expressed as

(pn) + (qm) for some integers p and q. This linear combination of n and m is also a multiple of 3, because

                                      pn + qm = p(3r) + q(3s) = 3(pr + qs).

Thus, if m and n have a common factor of 3, we can bring water back only in amounts between 0 and (n + m) that are also multiples of 3. This same argument will hold for any common factor of n and m. To have a chance to bring back all possible whole number amounts between 0 and (n + m), our water buckets must have no common factors other than 1. In other words, to obtain all possible whole numbers of gallons, it is a necessary condition that n and m are relatively prime.

Santa will leave to you the details of showing that we can actually generate all possible amounts when n and m are relatively prime (that is, that n and m being relatively prime is not only a necessary condition but also sufficient).

By the way, the water bucket conundrum models a powerful result in number theory, which says that if n and m are relatively prime, then there exist two other integers p and q such that pn + qm = 1. That is, with relatively prime bucket sizes n and m, there is a linear combination of n and m that will enable us to carry back exactly 1 gallon of water from the well. If we can get a 1 (or 1 gallon), we can get all the other numbers up to n + m, too.