Consider two problems you’ve probably heard before:

• Given a five-gallon bucket and a three-gallon bucket, measure exactly four gallons of water.
• Given a five-minute hourglass and a three-minute hourglass, measure exactly seven minutes.

These problems are clearly related, but how? Well, I’ll tell you how — by the good old GCD. Here’s my method for solving these problems:

• Let N and M be the two numbers for the measures you have (3 and 5 in the above problems). Let A be the amount you want to measure.
• Find d = gcd(N,M). If A is not a multiple of d, the problem is impossible. In our cases, we have d = 1, so we’re good.
• Find integers a, b (possibly negative) such that A = aN + bM. This is always possible, as A is a multiple of d. Usually it can be solved by inspection, but you can always go for the Euclidean algorithm if you’re stuck. For example, we have 3 * 3 – 1 * 5 = 4 (also 2 * 5 – 2 * 3) and 2 * 5 – 1 * 3 = 7.
• Use the linear combination to solve the problem! (Wait, what?)

The last step is the hardest to understand. Let’s start with the buckets. We interpret a positive bucket as filling a bucket with water, and a negative bucket as pouring one out. So if we use the linear combination 3 * 3 – 1 * 5 = 4, we will have to fill 3 three-gallon buckets with water, and pour out 1 five-gallon bucket. Specifically:

1. Fill the three-gallon bucket and pour it into the five-gallon bucket. ( 1 * 3)
2. Fill the three-gallon bucket again, and pour enough of it into the five-gallon bucket until the five-gallon is full (2 * 3).
3. Pour out the five-gallon bucket. (2 * 3 – 1 * 5)
4. Fill up the three-gallon bucket. Now you’ve got four gallons! (3 * 3 – 1 * 5).

That’s fairly easy to understand, because it’s easy to interpret a “negative bucket” as pouring out water. For the hourglass problem we have to figure out how to measure “negative time.”

We’ve got a five-minute hourglass and a three-minute hourglass. We can subtract them to make two minutes: turn them both over at the same time. When the three-minute one is done, there will be two left in the five-minute one. If we then flip over the three-minute timer and wait until the five-minute one finishes, flip over the three-minute one to get two additional minutes. See what we did there? We measured the difference between the three-minute timer and the five-minute timer inside the three-minute timer.

How does this apply to our problem? We’ve got 2 * 5 – 1 * 3 = 7. Let’s separate that as 1 * 5 + ( 1 * 5 – 1 * 3) and interpret this as “Start the five-minute timer and three-minute timer at the same time. Take the difference in the three-minute timer and add it on at the end.” Easy-peasy!

Challenge questions (all apply to both hourglasses and buckets):

• Given a four-minute hourglass and a seven-minute hourglass, measure nine minutes.
• Given a three-minute hourglass and a seven-minute hourglass, measure nine minutes.
• Given a two-minute hourglass and a seven-minute hourglass, measure nine minutes.