Water Jug Problem

Water Jug Problem is a famous puzzle that has many variations. One of the most famous one is that you are given 3-gallon bucket, 4-gallon bucket and unlimited supply of water. You are allowed to empty and fill the buckets and pour from one to another one. How can you measure 2 gallons of water using the two buckets?

In case you haven't come up with the solution yet. Here it is. Let (bucket1, bucket2) be the amount of water in each bucket, then to get 2 gallons in 4-gallon bucket.

That was easy, but what happens when you have -gallon and -gallon bucket?

Can you measure all numbers of gallons up to n with m-gallon and n-gallon bucket?

You can measure all numbers of gallons up to n as long as and are relatively prime, that is . If and are not relatively prime, you can measure only number of gallons that are multiples of their greatest common divisor.

How do you find a solution that measures x number of gallons?

You have to create a tree, where every node holds number of gallons in each bucket and has six branches. Every branch stands for one allowed move – fill bucket1, fill bucket2, empty bucket1, empty bucket2, pour from bucket1 to bucket2, pour from bucket2 to bucket1. If the new combination is already in the tree (you can use breadth search first to find it), do not add it to the tree. You can stop building your tree once there are no other nodes to add or once you find number of gallons in one bucket.

Is there anything special about the tree?

Every tree has nodes. That is because the tree contains every possible combination exactly once. Every tree has 2 main branches one from fill bucket1 and the other one from fill bucket2. Both branches have the same length .

You can see how tree looks like on Figure 2b. Figure 2a shows plotted graph in xy-coordinates.

Is there anything special about the bucket operations?

At any given moment at least one bucket is either full or empty. For example, when there are buckets , it is not possible to get combination .

Because at any given moment at least one bucket is either full or empty, all bucket operations are reversible. Every operation has its inverse (fill bucket1 - empty bucket1, fill bucket2 - empty bucket2, pour from bucket1 to bucket2 - pour from bucket2 to bucket1). For example, when there are buckets and the current combination is . When you pour from bucket1 to bucket2, you get . This operation can be reversed by pouring from bucket2 to bucket1. Then you get and that is the combination you had before applying pour from bucket1 to bucket2.

How is the graph plotted in xy-coordinates?

See the animation below. Every move stands for one of the allowed operations - fill bucket1, fill bucket2, empty bucket1, empty bucket2, pour from bucket1 to bucket2 and pour from bucket2 to bucket1. Note that the animation doesn't contain because this point can be in either branch and it was distracting from the symmetry.

Does the plotted graph in xy-coordinates depends on parity of m and n?

Yes, the graph looks different based on parity of m and n:

• m is even, n is odd: The middle vertical line is missing.
• m is odd, n is odd: The middle diagonal is missing.
• m is odd, n is even: The middle horizontal line is missing.

Is the plotted graph in xy-coordinates symmetric?

Yes, it is. Note that when you flip point about horizontal line and then flip it again about vertical line, you get point that is colored with the other color.

Is it possible to find out last node of each branch of the tree?

Yes. The last element of each branch depends on the parity of m and n. See table below.