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.