Eight Litres, Shared Evenly

  • Medium
  • Measuring and weighing
  • Tests: Searching a small state space by hand

The puzzle

An 8-litre jug is full of wine. There are two empty jugs holding 5 and 3 litres. None has any markings, and wine may only be poured from one jug to another until the source empties or the destination fills.

Divide the wine into two equal 4-litre shares. How few pours are needed?

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

Write each state as three numbers. From (8,0,0) there are only two first moves.

Hint 2

Every legal pour either empties the source or fills the destination, so there are few options at each step - the space is small enough to search.

Show the answer Hide the answer

Seven pours: (8,0,0) → (3,5,0) → (3,2,3) → (6,2,0) → (6,0,2) → (1,5,2) → (1,4,3) → (4,4,0).

How to get there

Fill the 5 from the 8, leaving (3,5,0). Fill the 3 from the 5: (3,2,3). Empty the 3 back into the 8: (6,2,0). Pour the 2 into the 3: (6,0,2).

Fill the 5 from the 8: (1,5,2). Top up the 3 from the 5, which takes 1: (1,4,3). Empty the 3 into the 8: (4,4,0). Done.

Seven is the minimum, which a breadth-first search of the states confirms - there are only 24 reachable states in all. Note that every reachable amount is a multiple of 1, the greatest common divisor of the jug sizes; with jugs of 6 and 4 only even amounts are reachable, so splitting an odd total would be impossible.

The technique worth keeping

Write the state as a tuple and list the legal moves from it. Pouring puzzles have tiny state spaces, so a systematic search beats cleverness - and the gcd of the jug sizes tells you in advance which amounts are reachable at all.