Making the water gallon brainteaser rigorous

Question

This is a classic brainteaser. Suppose I have two water jugs of size 4 gallons and 7 gallons, and an infinite amount of water supply.

I'm allowed to fill up a gallon completely, pour water into a a jug until the jug is full, and empty the water gallons. The question asks to find a way to measure 5 gallons. There are two ways I've figured out.

Method 1:

1. Fill and pour the 4 gallon into the 7 gallon to obtain 0/4, 4/7
2. Fill and pour the 4 gallon into the 7 gallon to obtain 1/4, 7/7
3. Empty the 7 gallon and pour the 1 gallon into the 7 gallon to obtain 1/7
4. Fill and pour the 4 gallon into the 7 gallon to obtain 5/7

Method 2:

1. Fill and pour the 7 gallon into the 4 gallon to obtain 4/4, 3/7
2. Empty the 4 gallon and pour the 3 gallons to obtain 3/4, 0/7
3. Fill the 7 gallon and pour into the 4 gallon to obtain 4/4, 6/7
4. Empty the 4 gallon, then pour the 6 gallons into the 4 to obtain 4/4, 2/7
5. Empty the 4 gallon and pour the 2 gallons to obtain 2/4, 0/7
6. Fill the 7 gallon and pour into the 4 gallon to obtain 4/4, 5/7

My question is how to make this rigorous. How do we find explicitly all the ways to measure 5 gallons, and prove that these are the only ways to obtain 5 gallons?

Moreover, can this be generalized? Given an arbitrary number of jugs of arbitrary size, what sizes can I measure out, and how many ways are there to do so?

I suspect this may have something to do with modular arithmetic, or maybe representing this problem as a graph, but I am stuck.

Answer 1

I would approach this as a problem in finding paths through a graph.

Let the vertices of the graph be the pairs $\def\gn#1#2{\left\langle {#1}, {#2}\right\rangle}\gn ab$ where $0\le a\le 4$ and $0\le b \le 7$. Directed edges on the graph from $\gn ab$ are of three types:

1. To $\gn 0b$ and $\gn a0$, for emptying a bucket.
2. To $\gn 4b$ and $\gn a7$, for filling a bucket.
3. To $\gn {a+x}{b-x}$, where $x=\min(4-a, b)$, for pouring bucket 7 into bucket 4, and to $\gn {a-y}{b+y}$, where $y=\min(a, 7-b)$, for pouring bucket 4 into bucket 7.

We can trim the graph to omit all the nodes that are not reachable from the initial position $\gn 00$, and all the edges incident to those nodes. For example, there is no way to reach position $\gn 11$, which has 1 gallon in each bucket. (To see this, just ask what the quantities could have been just prior to the last move.)

The edges are directed, and we can do a breadth-first enumeration of the nodes reachable from the initial position $\gn00$, and delete all the "back edges", which are edges that point from a node back to a previously-visited node. These correspond to suboptimal solutions for example, suppose we know a sequence of moves $S$ that solves the problem from position $\gn 40$. Then a complete solution starting from $\gn 00$ is: fill bucket 4, then do $S$. Another complete solution starting from $\gn 00$ is: Fill bucket 7, then fill bucket 4, then empty bucket 7, then do $S$. Eliminating the "back edge" from $\gn47$ to $\gn40$ removes this solution from the graph.

We then get something like this:

The blue node $\gn 00$ at the far left is where we start. The green nodes are nodes of interest where we have measured exactly $n$ gallons into bucket 7, for various $n$. The solution you want, $\gn05$, is the rightmost green node on the bottom path. We see that there is exactly one solution with minimal moves, corresponding to the one path from the blue node $\gn00$ to this green node.

Your alternative solution through $\gn43, \gn30, \gn46, \gn42, \gn 20, \gn45$ is the other path through the graph, along the top row of nodes, and then against the arrows after reaching $\gn20$ on the far right.

If you want to find all the ways to measure 5 gallons, you can leave in the back edges. Then the graph is much more complicated:

Node $\gn 50$ is the red node in the middle of the diagram. I left in the back edges, except the ones leading back to the starting position $\gn 00$. There are now an infinite number of solutions, all of them silly variations on the unique shortest solution, which you can see snaking its way along the middle. For example, after you get to $\gn 44$ you can empty bucket 4 and refill it again as many times as you want before continuing onward to $\gn 17$. Later once you get to $\gn 41$, you can return to $\gn 40$, essentially starting over.

Answer 2

The classic solution is programmed at the Water Pouring Problem demonstration. For this case, you make a 60-degree parallelogram with sides 4 and 7, label the sides with 0 to 7 and 0 to 4, and start a beam on the 120 degree corner.

As the beam hits the sides of the parallelogram, it marks out steps in the solution.