Solution
The Die Hard Jugs
Show the problem again
You have an unmarked 3-gallon jug, an unmarked 5-gallon jug, and an unlimited water supply. A step is one of: filling a jug from the source, emptying a jug onto the ground, or pouring one jug into the other until the source is empty or the target is full. What is the minimum number of steps needed to end up with exactly 4 gallons in the 5-gallon jug?
Worked solution
The answer is 6 steps: fill the 5 (1), pour it into the 3, leaving 2 (2), empty the 3 (3), pour the 2 gallons into the 3 (4), refill the 5 (5), and top off the 3: that takes exactly 1 gallon, leaving 4 in the 5-gallon jug (6). A breadth-first search of the state space confirms no shorter sequence works. It's solvable at all because gcd(3, 5) = 1, so every integer amount up to 5 is reachable.
Source: Classic water-jug measuring puzzle, versions of which appear in Bachet (1612); popularised by the film 'Die Hard with a Vengeance' (1995). Statement written for AxiomIQ.