The Water-Jug Puzzle

Definition The water pouring puzzle, also called the water jug puzzle, gives two jugs without markings whose capacities are $a$ and $b$ liters, where $a$ and $b$ are positive whole numbers. Both jugs start empty, and there is an unlimited supply of water and a drain. Three kinds of actions are allowed. You may fill a jug from the supply until it is full, empty a jug completely into the drain, or pour from one jug into the other until the first jug is empty or the second is full, whichever happens first. No other way of stopping a pour is allowed. The goal is to leave a given amount of water in one of the jugs. In the classic case the jugs hold 5 and 3 liters and the goal is exactly 4 liters in the 5-liter jug. This can be done in six actions, and a search through every state the jugs can reach shows that no shorter sequence works. Which amounts can be reached for other capacities is settled by the greatest common divisor, in the last card below.

Definition In the water pouring puzzle an amount is measured exactly when the allowed actions alone produce it, without judging a water level by eye. Every allowed action stops at a boundary, a jug that is full or empty, so its result follows from the capacities and the current amounts. Record the situation as a state $(x, y)$, where $x$ and $y$ are the amounts in the first and the second jug. Filling a jug sets its amount to its capacity, and emptying it sets its amount to $0$. Pouring the first jug into the second, whose capacity is $b$, moves

liters, the smaller of the amount in the first jug and the room left in the second, and leads to the state $(x - m,\ y + m)$. A pour the other way works the same with the roles of the jugs exchanged. After every action at least one jug is full or empty.

Definition For whole numbers $n \ge 0$ and $d \ge 1$, the number $n$ is a multiple of $d$ when $n = kd$ for some whole number $k \ge 0$. Then $d$ is called a divisor of $n$, and we say $d$ divides $n$. The sum of two multiples of $d$ is a multiple of $d$, and so is the difference of a larger multiple and a smaller one. In the water pouring puzzle this gives an invariant, a property that no allowed action can break. If $d$ divides both capacities, then every amount that ever appears in either jug is a multiple of $d$. Filling gives a capacity, emptying gives $0$, and a pour moves $\min(x, b - y)$ liters, which is a multiple of $d$ whenever $x$, $y$ and $b$ are.

Definition The greatest common divisor of positive whole numbers $a$ and $b$, written $\gcd(a, b)$, is the largest whole number that divides both of them. It decides the water pouring puzzle under the rules above, with positive whole-number capacities $a$ and $b$, two jugs that start empty, an unlimited supply and drain, and pours that stop only when the jug being poured from becomes empty or the jug being poured into becomes full. Let $g = \gcd(a, b)$. Then the jug of capacity $a$ can be left holding exactly $t$ liters if and only if $t$ is a multiple of $g$ with $0 \le t \le a$, and the same holds for the jug of capacity $b$, with $b$ in place of $a$. The two jugs together can hold any multiple of $g$ from $0$ to $a + b$, and no other amount. The theorem depends on these rules. Variants with different rules, for example jugs that start full with no supply or drain, need their own analysis.