# Making the water gallon brainteaser rigorous

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.

• I think you can view this as finding solutions to the Diophantine equation $4x+7y=5$ and then it is a matter of interpreting the results properly en.wikipedia.org/wiki/Diophantine_equation Jan 23, 2014 at 2:58
• With two jugs, after you've made your choice of which jug to fill at the start you have no more decisions to make, so the "brainteaser" is actually really easy. At each step, either (i) one of the jugs is full: pour as much as possible into the other; or (ii) one of the jugs is empty: fill it. With three or more jugs it gets more interesting, I assume.
– user856
Jan 23, 2014 at 2:58
• The more or less general problem (arbitrary relatively prime capacities) has been asked and answered recently. Jan 23, 2014 at 4:24

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.

• How do you prove that the graph contains all possible combinations for two buckets? Nov 15, 2015 at 23:07
• By construction: it includes an edge for every possible legal move, so every possible solution is represented as a path in the graph.
– MJD
Nov 18, 2019 at 15:43

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.