Four gallons from a 3 and a 5
You have an unlimited supply of water, an empty 3-gallon jug and an empty 5-gallon jug, neither with any markings. One step is one of:
- fill a jug completely;
- empty a jug completely;
- pour from one jug into the other until the first is empty or the second is full.
What is the smallest number of steps after which one of the jugs holds exactly 4 gallons?
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
Write the state as (gallons in the 3-gallon jug, gallons in the 5-gallon jug) and explore it step by step.
There are two natural starts: fill the 5, or fill the 3. Try both.
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. Search the states in order of the number of steps. Starting by filling the 5-gallon jug reaches 4 gallons in 6 steps; starting with the 3-gallon jug takes 8.
A 6-step solution. Writing (3-gallon jug, 5-gallon jug):
- Fill the 5: (0, 5).
- Pour the 5 into the 3: (3, 2).
- Empty the 3: (0, 2).
- Pour the 5 into the 3: (2, 0).
- Fill the 5: (2, 5).
- Pour the 5 into the 3 until it is full: (3, 4).
Why not fewer. From (0, 0), the states reachable in at most 5 steps are, besides the start: (3, 0), (0, 5); then (0, 3), (3, 5), (3, 2); then (3, 3), (0, 2); then (1, 5), (2, 0); then (1, 0), (2, 5). None contains a 4. So 6 is the minimum.
The other route. Starting by filling the 3: (3, 0), (0, 3), (3, 3), (1, 5), (1, 0), (0, 1), (3, 1), (0, 4). That is 8 steps.