# Water Jug Problem

• Sep 12th 2010, 07:39 PM
My Little Pony
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?
• Sep 12th 2010, 07:50 PM
undefined
Quote:

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 $-56\equiv 12 \pmod{17}$. 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.
• Sep 12th 2010, 07:55 PM
My Little Pony
Quote:

Originally Posted by undefined
Notice that $-56\equiv 12 \pmod{17}$.

17 does not divide -44?
• Sep 12th 2010, 07:59 PM
My Little Pony
Ah, excuse my previous post. I am an idiot. :)
• Sep 12th 2010, 08:03 PM
My Little Pony
Quote:

Originally Posted by undefined
Notice that $-56\equiv 12 \pmod{17}$. 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.
• Sep 12th 2010, 08:15 PM
undefined
Quote:

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 $-7 \cdot 12 \equiv 1 \pmod{17}$ which for our purposes we can rewrite $10 \cdot 12 \equiv 1 \pmod{17}$. 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\cdot12\equiv b\pmod{17}$ -- a is the number of times we fill the small jug, and b is the target.

And for completeness, $10 \cdot 12 \equiv 1 \pmod{17} \implies 80\cdot12 \equiv 12\cdot12 \equiv 8\pmod{17}$.

Alternatively, $-7 \cdot 12 \equiv 1 \pmod{17} \implies -56 \cdot 12 \equiv 12\cdot12\equiv8\pmod{17}$.
• Sep 12th 2010, 08:30 PM
undefined
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 $40\equiv4\pmod{12}$.

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.
• Sep 12th 2010, 08:42 PM
undefined
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).