Ever played one of those games where you are given two water containers/jugs of different sizes and the task is to fill one of the jugs with a certain amount of water? Here’s an android app (image below) for the game if you aren’t familiar. Play it all you want because now I’m going to ruin it for you! I’m going to tell you a general solution to this water jug riddle.

The only thing you need to know is: Greatest Common Divisor.

Let me take the help of an example to explain the general solution. Take two containers of size 15 and 24 units. Can you put 6 units water in the 15 unit jug?

By definition, we know that *gcd*(15,24) = 3

Another interpretation of *gcd* is that it is the smallest positive linear combination of the two numbers. Here, the linear combination would be:

2*24 – 3*15 = 3

We can prove that *gcd* is in fact the smallest positive linear combination that is possible. Check out *Proof I* below.

If you are convinced, let’s move on to solving the water jug puzzle. My claim is that, if the units of water you are supposed to finally produce in one of the jugs is a multiple of the *gcd* of the two jug capacities, then it can be done else it can’t be! (*Proof II *below)

Here’s how: Just represent the number as a linear combination of the jug capacities. The catch is there can by multiple representations of the same number, you have to choose the best one.

So in the example above, one of the ways 6 can be represented is as follows:

6 = 2 * 3

9 = 2 * (2*24 – 3*15)

6 = 4*24 – 6*15

Once you know the constants involved in the linear combination, here 4 and 6, the puzzle becomes a mechanical exercise of following the algorithm below:

- Fill the 24 unit jug with water completely.
- Pour water from 24 unit jug into the 15 unit jug to fill it.
- Whenever the 15 unit jug becomes full, empty it and pour water from 24 unit jug into it again.

So what we did here is fill the 24 unit jug 4 times. We emptied 15 units of water in one time and stopped when the water was less then 15 units. So, 4*24 = 96 units was water added, and the maximum we could remove was 6*15 = 90 units. Which leaves the remaining 6 units in whichever jug you want it to be!

Sounds good, but it is much simpler than this! You don’t even need to know the constants involved in the linear combination. Simply follow the above algorithm of filling up one jug and pouring contents into the other, emptying it when full and you’ll eventually reach the solution! Just keep track of the amount of water in both jugs after every move to know when you’re there.

Moreover, you need not worry about which jug you should fill and which jug you should empty. So for the above example, we were earlier filling the 24 unit jug and emptying the 15 unit one. You could reverse it too.

2*15 – 1*24 = 6

So, start filling the 15 unit jug and pour the contents into 24 unit jug, emptying it when full. Following the filling step just 2 times in this case, we arrive at the solution!

So no matter where you start from, following the mechanical exercise you would eventually reach the desired amount of matter in the jugs, but the number of moves you incur may not be optimal. Most of these games want you to get the result in least number of steps, so depending upon the jug you choose to fill, you can get the lesser number of overall moves. Go try it!

**Proof I**

Say we have two numbers x and y. Let the smallest positive linear sum be denoted by *ax + by*, where *a* and *b* are some fixed constants. And let the *gcd*(x,y) = m.

Now, we know by definition that *m* divides *x* & *y*. So *m* divides any linear combination of *x* & *y* too. Hence *m* divides *ax+by*.

Therefore, m <= ax + by.

Next, we’ll show that ax + by <= m and therefore, m = ax + by implying *gcd* is the smallest positive linear sum of the two numbers.

Say we divide *x* by *ax+by*. We will get a quotient *q* and a remainder *r*.

x = q(ax + by) + r

r = (1-qa)x + (-b)y

so we get *r* as a linear combination of *x* & *y*. But we already know that *ax+by* is the smallest linear combination so *r* is a multiple of *ax+by*. Also by definition of the remainder, *0 <= r < ax + by*. Therefore, *r = 0* is the only possibility that remains.

Hence *ax + by* divides *x*. Similarly, *ax + by* divides *y*. This means that

*ax + by* is a common divisor of *x* & *y*. Therefore, *ax + by* <= *m*. Hence *m = ax + by*.

**Proof II**

To prove that you can’t produce an amount of water in the jugs that

isn’t a multiple of the *gcd *of the jug capacities, consider this:

We know that any amount of water that is present in either of the jugs is a linear combination of the two jug capacities. From *proof I* we also know that all the linear combinations are multiples of the *gcd*. So, we can never produce an amount in any of the jugs that isn’t a multiple of their *gcd*.

I remember you mentioning this long back! 😀

seems nicely written. I shall read it in peace this evening 🙂

Cool 🙂

Brilliant stuff i have an exam in less then 8 hours, reading the solution to the problem gave me a confidence that i can ace the exam.

PS: I am computer science student and maybe i need to write a code to implement the above scenario. So Yeah. And you seem younger than High school pass out.

Bottom line: Brilliantly written keep up the good work. cheers

Glad that you liked it. And no, I’m quite older. 🙂

I have a doubt you proved that we cannot get any amount of water in any of the jugs which is not a linear combination of a and b . But this does not proves that we can always make a linear combination of water in one of the jugs! Am I right or missing the point?

So how to find value of constants with single equation.

24a-15b=6

When gcd is 1 then in every case it will show result but that should not be the case

Is it mean that the water jug problem with a units and b units has a solution if and only if

gcd(a,b) = target units

or

the target units is divisible by the gcd(a,b) where gcd(a,b) must be smaller than the target units.

Gr8 explanation! Thanks 😀