Five, Three, and Exactly Four
In the kitchen there are two jugs: one holds 5 litres, the other 3 litres. Neither has a single mark on it, so the only amounts you can ever be sure of are "completely full" and "completely empty".
The tap runs as much water as you like, and the sink takes as much as you like away. The recipe needs exactly 4 litres.
Fill, empty, or pour one into the other until it stops.
You are allowed exactly three kinds of move, and each one counts as a step:
- fill a jug to the brim from the tap;
- empty a jug into the sink;
- pour one jug into the other until either the first is empty or the second is full.
Answer to type: the smallest number of steps that leaves exactly 4 litres in one of the jugs.
💡 I want a nudge
There are two different routes to 4 litres. One of them is one step shorter than the other — try starting with the small jug.
Log in to send an answer
Reading is free for everyone. Sealing an answer, earning points and appearing on the solver wall need an account.
Log in🔓 The solution
Answer: 6
Writing each state as (big, small):
- Fill the small jug → (0, 3)
- Pour it into the big one → (3, 0)
- Fill the small jug again → (3, 3)
- Pour into the big one until it is full. The big jug takes only 2 more litres, so 1 litre stays behind → (5, 1)
- Empty the big jug → (0, 1)
- Pour the 1 litre across, fill the small jug and pour it in — the standard route needs one more fill here, but the shorter way is to start over from (0, 1): pour it into the big jug, then fill and add the small jug once more → 1 + 3 = 4 litres. Six steps.
The other route — fill the 5, pour into the 3, leaving 2; empty the 3; move the 2 across; fill the 5; top up the 3, which takes 1 — also lands on 4 litres, but in the big jug and after more moves.
The trick: 4 = 3 + 3 − 2 and also 4 = 5 − 3 + … — every reachable amount is a combination of 5s and 3s added and taken away. Since 5 and 3 have no common factor, every whole number of litres up to 5 is reachable. Two jugs of 4 and 6 could never give you an odd litre at all.