Learn / Library / Brainteasers
Reachable cup states
buckets hold and litres. Both start empty. The only operations are: fill one bucket to the brim from a tap, empty one bucket completely, or pour from one bucket into the other until the source is empty or the target is full. A state is the pair of current contents (litres in the -litre bucket, litres in the -litre bucket). How many different states, including the starting one, can be reached by some sequence of operations?
Checking an answer needs JavaScript. The hint and the solution open without it.
Hint
Every amount is a multiple of one common number, and after each operation at least one bucket is full or empty.
Solution
- Every amount ever held is a multiple of , so the small bucket holds , or litres and the big one , , or , which gives candidate pairs.
- After any operation one bucket is full or empty, which rules out the pairs (, ) and (, ), so at most pairs remain.
- A search from the empty pair shows that each of the other pairs is reached, such as (, ) via the sequence fill the big bucket, pour into the small bucket, empty the small bucket, pour again.
- So the number of reachable states is .
Answer: