Is there a general solution to the water-bucket logic problem? (see details)
The water-bucket problem is a logic problem that states “Given two buckets that each hold 3 and 5 litres, how to you measure a quantity of 4 litres?”
Each step in the solution can be one of three things: Fill up a container all of the way, empty a container completely, or use one container to fill up another as much as possible.
The solution to the original problem is:
Fill the 5 litre bucket (completely). The buckets are now 5/5 and 0/3.
Pour the 5 litre bucket into the 3 litre one. They are now 2/5 and 3/3.
Empty the 3 litre bucket. They are now 2/5 and 0/3.
Pour the 5 litre bucket into the 3 litre one. They are now 0/5 and ⅔.
Fill the 5 litre bucket. They are now 5/5 and ⅔.
Pour the 5 litre bucket into the 3 litre one. They are now 4/5 and 3/3.
Now, you have one bucket with the required amount of 4 litres.
Now for the actual question.
Given the sizes for the two buckets and the target amount, how can one tell whether there is a solution to the problem? Is there a standard algoritm to determine a possible solution, or even the shortest solution?
I’ve been thinking about this for a while, and I believe that it is always possible if the target amount is a multiple of the GCF of the two bucket sizes, and of course only if the largest bucket is at least as large as the target amount.
I think that a possible algorithm, although not the most efficient, might be the below algorithm. For each step, pick which one of the following options applies and do it.
1. If the largest bucket is completely empty, fill it up.
2. If the smallest bucket is completely full, empty it.
3. If neither of the above apply, pour the larger bucket into the smaller one.
Hopefully, the larger bucket should eventually contain the target value.
This question is in the General Section. Responses must be helpful and on-topic.