Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The problem:

Explain how to measure 8 units of water using only two jugs, one of which holds precisely 12 units, the other holding precisely 17 units of water.

Given the hint "Find $gcd(12,17)$", it is clear that since 17 is prime, $gcd(12,17)=1$. But I am not sure how that actually helps to solve the problem. I don't need a full answer , but just an idea of how to proceed. Anybody have ideas?

share|improve this question
    
Can you come up with a sequence of actions that change the amount of water step by step? What kind of pattern do you get? –  I like Serena Jul 12 at 17:39
1  
Hint: $17-12=5$, $17-(12-5) = 10$, $17 - (12-10) = 15$, $15 - 12 = 3$, $17 - (12-3) = 8$. –  Winther Jul 12 at 17:44
1  
Google "decanting problems" and you will find a vast amount of information on these types of problems. –  David H Jul 12 at 17:59
    
Yeah I knew how to do it with the step-by-step way where you fill up your larger jug and then fill up/empty the smaller jug until your larger jug is empty. I just was not sure how to do it just straight from gcd –  Savage Henry Jul 12 at 18:00

2 Answers 2

up vote 5 down vote accepted

First, for any jug problem with jugs of capacities $X$ and $Y$ with $g=\gcd(X,Y)$, you can only end up with quantities of water that are multiples of $g$ after any number of operations (check that every operation you perform conserves the residual respect to $g$). Therefore, the hint has a point of making you realize this connection. In this case you learn that there exists a solution but there's more, which brings me to...

... Second, once you realize this connection, then you know you can write an integer equation $aX+bY=ng$ where one of ${a,b}$ is positive and the other one is non-positive, and $n$ is the desired factor to reach your goal multiple of $g$. I will not solve this equation for your example but I will tell you how to continue once you do. Let's say $a$ is the positive one (since I am not assigning values to $X$ and $Y$, there's no loss of generality), then I can think of $a$ as filling up $X$ and $b$ as emptying $Y$. How do you operate then?

Fill $X$ up, and pour it into $Y$. Every time $Y$ fills up, throw the water away, and continue pouring $X$ into $Y$. After $a$ times you have filled $X$ and poured it into $Y$, and you had thrown the water away $b$ times, then you have $ng$ gallons of water in one of the jugs. Which one will depend on whether you reach $a$ or $b$ first.

This is NOT the most efficient way, but it is what shows the connection between the jugs problems and the $\gcd$. It also lets you know whether it is possible to solve.

share|improve this answer

See Bézout's identity. This series of equations closely follow a gcd algorithm for 12 and 17.

$$\begin{align} \text{(1)}&& 17a - 12b = 8 \\ \text{(2)} && \text{Let } c = b - a \\ \text{(3)} && 5a - 12c = 8 \\ \text{(4)} && \text{Let } d = a - 2c \\ \text{(5)} && 5d - 2c = 8 \\ \text{(6)} && \text{Let } e = c - 2d \\ \text{(7)} && d - 2e = 8, \text{ so } d = 8 + 2e \\ \text{(8), from (6) and (7)} && c = 16 + 5e \\ \text{(9), from (4), (7), (8)}&& a = (8+2e) + 2(16+5e) = 40 + 12e \\ \text{(10), from (2), (8), (9)}&& b = (16+5e) + (40 + 12e) = 56 + 17e \end{align} $$

Set $e = -3$ and you get $a = 4, b = 5$. Fill the 17-jug 4 times and empty the 12-jug 5 times and you get $4\cdot17 - 12\cdot5 = 68 - 60 = 8$ units.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.