Thread: Water Jug Problem

You take a 17 quart jug and a 12 quart jug to a stream, but you want to bring 8 quarts of water back. How do you do it?

Attempt at a solution

I used Bezout's Identity for this:

8 = 17x + 12y

However, the GCD of (12, 17) is 1. So:

1 = 17x' + 12y'

Using Bezout's Identity, I get:

x' = 5, y = -7

Therefore, x = 40, y = -56.

According to this result, I have to fill the 17 quart jug 40 times and pour into the 12 quart jug 56 times. That seems pretty excessive. Can anyone tell me what I'm doing wrong?

Originally Posted by My Little Pony

You take a 17 quart jug and a 12 quart jug to a stream, but you want to bring 8 quarts of water back. How do you do it?

Attempt at a solution

I used Bezout's Identity for this:

8 = 17x + 12y

However, the GCD of (12, 17) is 1. So:

1 = 17x' + 12y'

Using Bezout's Identity, I get:

x' = 5, y = -7

Therefore, x = 40, y = -56.

According to this result, I have to fill the 17 quart jug 40 times and pour into the 12 quart jug 56 times. That seems pretty excessive. Can anyone tell me what I'm doing wrong?

Notice that . This means you can get to 8 by filling the smaller jug 12 times from the river total. See here for a more elementary working of a similar problem.

Originally Posted by undefined

Notice that .

I'm a little confused about this.

17 does not divide -44?

Ah, excuse my previous post. I am an idiot.

Originally Posted by undefined

Notice that . This means you can get to 8 by filling the smaller jug 12 times from the river total.

I am confused however, as to how you came to this conclusion.

Originally Posted by My Little Pony

I am confused however, as to how you came to this conclusion.

Your solution to Bezout's was of course correct, 5*17 - 7*12 = 1.

Look at it as which for our purposes we can rewrite . This means if we fill the small jug 10 times and empty everything into the large jug (we will have to empty the large jug 7 times in the process) we will be left with 1 quart left in the large jug. Similar holds for any other positive integers a and b where b < 17 and -- a is the number of times we fill the small jug, and b is the target.

And for completeness, .

Alternatively, .

Probably should have mentioned that we can also fill the large jug and empty into the small jug, in which case we need to fill it 4 times since .

Note that 4*17 - 5*12 = 8.

Might have reduced confusion if I'd mentioned this at the beginning, however my mindset was of filling the smaller jug because of the other thread I referenced.

One last observation. Note that since gcd(12,17) = 1 Bezout's identity gives us the modular inverse of 12 (mod 17) and the modular inverse of 17 (mod 12).