Learn / Library / Brainteasers
Splitting the syrup
A barrel with litres of syrup stands beside an empty -litre jar and an empty -litre jar. None of the vessels has markings. A move is one pour from one vessel to another that continues until the source is empty or the target is full; nothing is spilled, and nothing is added or removed. What is the minimum number of moves needed to have exactly litres in the barrel and, in the -litre jar, also exactly litres?
Checking an answer needs JavaScript. The hint and the solution open without it.
Hint
Write the contents as a triple (barrel, big jar, small jar) with a total of at all times.
Solution
- Write the state as (barrel, -jar, -jar), starting at (, , ) and aiming for (, , ).
- One shortest sequence of states is (, , ), (, , ), (, , ), (, , ), (, , ), (, , ), (, , ), (, , ), (, , ).
- A search of all positions at smaller depth never reaches (, , ).
- This sequence has moves.
Answer: