Solving the Water Jug Problem

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.

waterlogic

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.

Advertisements

9 thoughts on “Solving the Water Jug Problem

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

  2. 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?

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s