Three and Five Make Four

Question

You have a 3-liter jug, a 5-liter jug, an unlimited tap, and a drain. Legal moves: fill a jug, empty a jug, or pour one into the other until the source is empty or the target is full. Produce exactly 4 liters in a jug, in the minimum number of moves.

Accepted Answer

Six moves, ending with 4 in the 5-jug. States as (3-jug, 5-jug): (0,0) to (0,5) to (3,2) to (0,2) to (2,0) to (2,5) to (3,4) fill 5 → pour into 3 → empty 3 → pour the 2 across → refill 5 → top off the 3 (only 1 fits, leaving 4). The mirror plan that starts by filling the 3-jug also works but takes 8 moves, breadth-first search over the 24 reachable states confirms 6 is minimal. Why 4 is reachable at all: every move changes the total by 0, pm3, or pm5, so any achievable amount is an integer combination 3a + 5b, and gcd(3,5) = 1 makes every integer expressible (here 4 = 2cdot5 - 2cdot3, visible in the solution: two fills of 5, two dumps of 3). With jugs of 6 and 9, only multiples of 3 are reachable, the gcd is the complete obstruction (Bézout), within the range the jugs can physically hold. Interview framing: small state space + legal moves = graph search. Saying "I'd BFS this, 24 states" and then exhibiting the 6-move path shows both the algorithmic and the closed-form view; the gcd invariant answers the inevitable "when is it impossible?" follow-up before it's asked.

Three and Five Make Four

Problem

Your answer

Hints

More Brainteasers & Logic to train on