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!
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.
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.