Friday, June 25, 2010

Two water jug problem : Existence of a solution

As you might have come across the following problem some day : 
There are two water jugs, each with a different capacity, say A and B, B>A.
And the basic operations are defined on them : 
Empty A, Empty B, Pour A into B, Pour B into A, fill A, fill B
with an unlimited supply of water to fill the jugs.

Is there way to check, whether a solution does exist, If I want
to measure a quantity C using A and B?

One way is to check exhaustively for all possible states.
But I am looking for something like this :
which has a way to check the existence of a solution for 3 jug problem.

Ans : 
Draw a rectangle A by B on a grid. 
You start at (0,0).
A valid move takes you from (x,y) to either (A,y) or (x,B) by filling one jug from the fountain; or to (0,y) or to (x,0) by emptying a jug; or to (x+d,y-d) by filling from one jug to the other - however, you do this until one is empty or the other is full, i.e. either x+d=0 or x+d=A or y+d=0 or y+d=B.

First we note that we start with coordinates that are multiples of gcd(A,B).
You will note that this condition remains intact, no matter what step is applied.
Hence by induction it will always be true that each jug contanis a multiple of the gcd.

Now for the opposite:
There are integers u, v such that A*u+B*v = gcd(A,B)
(one will be >0, the other <0).
Mark the point (A*u, B*v) in the plane and tile the plane with A by B rectangles as the one in the first part.
(A*u, B*v) is at the lower left corner of some tile.
Draw the line to (0,gcd(A,B)) - this is tilted by -45° because A*u+B*v = gcd(A,B)
Make transparent copies of all tiles haveing part of this line passing through them an stack them. The result is one A*B rectangle with a lot of -45° line segments from border to border (corresponding to valid "from one jug to the other" moves).
Each end point (except those corresponding to the start and end of the original line) corrsponds with an end point of another line segment at the opposite side o the rectangle - this comes from the fact that the original line continues at a neigbouring tile. And the move from one such end to the other corresponds to filling or emptying a jug.
In total you obtani frmo this a path / sequence of moves leading from (0,0) to (0,gcd(A,B))

Ans : 

let a be the amount of water in one jug, and b be the amount of space remaining in the other jug
then you can run the equivalent of this GCD algoorithm.

Ans : 
Ok, I finally see it.  Since the capacities A and B are relatively prime, there exist integer (x,y) that solve x*A + y*B = n for all integer n.  One of x and y will be negative, and the other positive.  The process is then one of filling an empty A a total of x times, pouring water from A to B whenever possible, and dumping a full B out a total of y times.  

After you have filled an empty A x times and dumped a full B y times, you will have n units of water leftover in the two jugs.

No comments:

Blog Archive