General Question

PhiNotPi's avatar

Is there a general solution to the water-bucket logic problem? (see details)

Asked by PhiNotPi (12262 points ) April 6th, 2012

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.

Observing members: 0 Composing members: 0

3 Answers

Thammuz's avatar

I’m just speculating but, given the quickest solution, (fill 5, use 5 to fill 3, empty 3, pour remianing 2 in 3, fill 5, use 5 to fill the remainder of 3, 5 contains 4) you’d have to have a gap between your target amount and the buckets that is the same in module for either bucket.

Second thoughts: i’m trying with some quantities that would be correct assuming my hypothesis is and it appears that, with my method, you can only get a quantity that is 1 less than the bigger bucket. So i’m certainly wrong, but maybe that’s the rule.

That’s all i’ve time for, i will try to elaborate on it during the day.

6rant6's avatar

If you can determine that there are a finite number of states for the system, you could use a transportation model to solve it.

You’d start at one end of the problem, and figure out the least moves to get to all adjacent states. Repeat until solved.

roundsquare's avatar

I think your algorithm is correct and I’m quite sure your solution (multiple of GCF) is correct.

There is a theorem that says something like this:
Let x and y, be two numbers such that GCF(x, y) is z. Then there is a formula of the form:
z = a * x + b * y
where a and b are both integers.

In fact, unless z = x or z = y, either a or b must be negative, but not both. (Because z < x, y).

Say a > 0 (and thus b < 0). Then you want to fill the x bucket a times and subtract out the y bucket b times. I’m a little tired right now but I think your algorithm does that. This gets you to z. If you keep going you can get 2z, 3z, etc…

Answer this question

Login

or

Join

to answer.

This question is in the General Section. Responses must be helpful and on-topic.

Your answer will be saved while you login or join.

Have a question? Ask Fluther!

What do you know more about?
or
Knowledge Networking @ Fluther