Results 1 to 8 of 8

Math Help - Water Jug Problem

  1. #1
    Member
    Joined
    Nov 2008
    Posts
    76

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by My Little Pony View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2008
    Posts
    76
    Quote Originally Posted by undefined View Post
    Notice that -56\equiv 12 \pmod{17}.
    I'm a little confused about this.

    17 does not divide -44?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2008
    Posts
    76
    Ah, excuse my previous post. I am an idiot.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2008
    Posts
    76
    Quote Originally Posted by undefined View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by My Little Pony View Post
    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}.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. water carton problem
    Posted in the Statistics Forum
    Replies: 2
    Last Post: May 19th 2010, 02:46 PM
  2. Replies: 3
    Last Post: February 15th 2010, 12:53 PM
  3. Water in Vase Problem
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: October 29th 2009, 03:34 PM
  4. Spring in water problem
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: April 17th 2009, 08:39 AM
  5. Replies: 4
    Last Post: October 22nd 2007, 05:19 PM

Search Tags


/mathhelpforum @mathhelpforum