A 3-litre jug, a 5-litre jug, exactly 4 litres.
The water jugs puzzle: with an unmarked 3-litre jug, an unmarked 5-litre jug, and a tap, measure exactly 4 litres. Solvable by fiddling, but the interview version asks why it works, which numbers are reachable, and what the shortest sequence is.
You have two jugs with no markings: one holds exactly 3 litres, the other exactly 5. A tap provides unlimited water, and a drain takes any amount away. The only operations are: fill a jug to the brim, empty a jug completely, or pour from one jug into the other until the source is empty or the destination is full, whichever comes first.
Measure exactly 4 litres into the 5-litre jug. Then answer the harder question: which whole-litre amounts are reachable at all, and why?
The first part yields to trial and error inside a couple of minutes, which is why interviewers rarely stop there. The second part is where the puzzle earns its place. Every operation leaves each jug either empty, full, or holding a quantity determined by the other jug's capacity, so the set of states is small and finite. Think of it that way, and "can I reach 4" becomes a question about a graph rather than about cleverness.
Stuck? Open hints one at a time
Each hint gives away one more layer. Stop the moment something clicks.
Hint 1 a nudge
Pouring a full 5 into an empty 3 leaves 2 in the big jug. That 2 is a quantity neither jug can hold on its own, so it must be preserved by moving it somewhere.
Hint 2 the key move
Park the 2 litres in the empty 3-litre jug. Now the 3-litre jug has exactly 1 litre of space left. Fill the 5 and pour into the 3: only 1 litre leaves.
Hint 3 for the reachability question
Every pour, fill, or empty changes the total water by 0, plus or minus 3, or plus or minus 5. So every reachable total is a combination of 3s and 5s. What does number theory say about which integers those combinations cover?
The solution
Reveal the full solution
Six moves, writing states as (3-litre jug, 5-litre jug):
- Fill the 5: (0, 5).
- Pour 5 into 3: (3, 2).
- Empty the 3: (0, 2).
- Pour 5 into 3: (2, 0).
- Fill the 5: (2, 5).
- Pour 5 into 3 until the 3 is full: (3, 4).
Four litres sit in the 5-litre jug. A mirror-image sequence that starts by filling the 3 also works in six moves, ending with (0, 4) after emptying the small jug; neither can be shortened, which brute force over the state graph confirms.
Reachability is the better half of the puzzle. Every operation adds or removes water in multiples of 3 or 5, so any reachable amount is 3a plus 5b for integers a and b, some of them negative. The set of such combinations is exactly the multiples of the greatest common divisor of 3 and 5, which is 1, so every whole number from 0 to 5 is reachable in principle, and a short search confirms each one in practice. Change the jugs to 4 and 6 litres and the greatest common divisor becomes 2, so odd amounts are impossible no matter how you pour. That is the theorem behind the fiddling: reachable if and only if the target is a multiple of gcd(a, b) and fits in the larger jug.
What this puzzle is really testing
Two things at once. First, whether you model the situation as a state space: a node for each (small, large) pair and an edge for each legal operation, at which point "shortest sequence" is literally shortest path, and breadth-first search hands you the six-move answer with a proof of minimality. The BFS versus DFS decision guide covers why breadth-first is the tool when the question is "fewest moves". Second, whether you can extract the invariant (totals are combinations of 3 and 5) that answers the impossibility question without any search at all.
Follow-ups to expect
Three jugs. Jugs of 7 and 11 and a target of 2. And the implementation question: write the search, which is a tidy exercise in graph traversal over implicit states, since the graph is never stored, only generated; the graphs module covers that pattern under implicit graphs. If you are asked for the minimal number of moves in general, the state space is only (a + 1) times (b + 1) nodes, so BFS is the whole answer.