Kinesys lands with a thud next to the Fountain of Fair Measure, the public well of Staterion, where the locals line up with jugs of every size. Here water is dispensed to the exact gallon: on Staterion, “roughly four gallons” is a phrase banned by law.
Liz needs exactly 4 gallons of water for the ship’s cooling system. The fountain keeper lends her two empty jugs: one holds 3 gallons, the other 5. No markings, no halfway lines, and the fountain’s big scale, by regulation, is only for the final check.
Dord finds this unacceptable: “Who makes jugs without markings?” Liz, trying not to lose her temper, breaks into a tap-dance step on the cobblestones. M00N waves enthusiastically at the line.
The Riddle
You have two jugs, both empty to start, holding 3 and 5 gallons respectively. You have all the water you want, and you can fill and empty the jugs as well as pour water from one into the other. You need to get exactly 4 gallons of water into the 5-gallon jug. How do you do it?
Hint
Filling and emptying isn’t enough: the secret is pouring from one jug into the other. Try to create and keep in-between amounts, such as what’s left in the 5-gallon jug after you use it to fill the 3-gallon one.
Solution
First fill the 5-gallon jug and pour 3 gallons into the 3-gallon jug: 2 gallons remain in the 5-gallon jug. Then empty the 3-gallon jug and pour the 2 gallons from the 5-gallon jug into it. Now fill the 5-gallon jug again and pour 1 gallon into the 3-gallon jug, which is then full. Exactly 4 gallons remain in the bigger jug.
To solve problems like this in general, it helps to represent each configuration as a pair of numbers (n1, n2), giving the gallons of water in the 3-gallon jug and the 5-gallon jug respectively. Then you build a graph whose nodes are these pairs: from each node, arrows lead to the nodes you get by applying one of the following rules:
- fill jug 1
- fill jug 2
- empty jug 1
- empty jug 2
- pour from jug 1 into jug 2
- pour from jug 2 into jug 1
The number of arrows leaving each node equals the number of rules that apply to that configuration. Once the graph is complete (taking care not to add nodes that already exist), all that’s left is to find the path from the starting configuration to the desired final one. In practice, you have built the state diagram of a finite-state machine, with two state variables (the contents of the two jugs) and six inputs (the rules); the machine’s output essentially coincides with its state.
In our case, the path to follow is:
(0, 0) → (0, 5) → (3, 2) → (0, 2) → (2, 0) → (2, 5) → (3, 4)
obtained by applying rules 2, 6, 3, 6, 2, 6.
At the final check, the fountain’s scale reads exactly 4 gallons, and the keeper waves Liz through with an approving nod.