# Jugs of water puzzle…

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?

• 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? – Klaas van Aarsen Jul 12 '14 at 17:39
• Hint: $17-12=5$, $17-(12-5) = 10$, $17 - (12-10) = 15$, $15 - 12 = 3$, $17 - (12-3) = 8$. – Winther Jul 12 '14 at 17:44
• Google "decanting problems" and you will find a vast amount of information on these types of problems. – David H Jul 12 '14 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 '14 at 18:00

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.

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.