Generalization of the two bucket puzzle - MathOverflow

Generalization of the two bucket puzzle

2009-11-17T07:58:03Z

The classic puzzle goes something like this: "You are standing in front of a lake with a 3 gallon bucket and a 5 gallon bucket, how can you get 4 gallons of water?"

Is there an easy way to generate the triple (A,B,C) where you can get C gallons of water using buckets of size A and B?

Answer by Nick Salter for Generalization of the two bucket puzzle

2009-11-17T08:27:41Z

Not an answer but rather a good thing to look at in connection with the problem-

http://numb3rs.wolfram.com/501/puzzle.html

Answer by Simon Wadsley for Generalization of the two bucket puzzle

2009-11-17T09:31:35Z

Yes. The answer follows from Bezout's theorem which says that given integers A,B and C, C can be written as XA+YB if and only if C is a multiple of the highest common factor of A and B. Euclid's algorithm tells you how to compute X and Y.

It is not too hard to see that the only volumes you can get are ones of the that are integer linear combinations of A and B and you can get every positive volume that arises in this way (as long as you have a large enough additional container to store it all).

Answer by Elizabeth S. Q. Goodman for Generalization of the two bucket puzzle

2009-11-17T10:24:59Z

Simon's answer points out that the Euclidean algorithm shows that gcd(A,B) divides C is necessary, but the lack of large container makes the problem more difficult, because obviously you can't get $C$ if $C \gt A+B$. However, the following modification of the algorithm seems to work.

Let's assume $A \lt B$ and gcd$(A, B)=1$ for simplicity. By pouring from B into A and dumping A, you can get any positive integer $B-nA$ left in B. Do this until the answer is less than $A$. Then by transferring the contents to bucket A and filling it from B into it, we get $2B-(n+1)A$. Then subtract $A$ again until you have $0 \lt 2B-kA \lt A$, and we can iterate this process to get $3B-(k+1)A$, etc. This gives any integer linear combination $rB-sA$ up to the size of $A+B$ because once you get the right multiple of $B$ into the combination, you can always add bucketsful of $A$.

You just need to get $rB\equiv C$ (mod A) in order to find a combination for $C$, which happens if gcd$(A, B)=1$. With this algorithm run in the general case you can get any multiple of gcd($A, B$) up to $A+B$ (this holds trivially when $A=B$).

(Sorry, I had to edit this answer several times because parts disappeared, until I realized that my inequality signs were being parsed as HTML tag starts even after dollar signs.)

Answer by Bob for Generalization of the two bucket puzzle

2010-04-27T15:11:58Z

Fill the 3 gallon bucket and pour it into the 5 gallon bucket. Fill the 3 gallon bucket again and pour as much as possible into the 5 gallon bucket without overflowing. Now you have a 3 gallon bucket with exactly 1 gallon of water in it. Now dump out the 5 gallon bucket and pour the 1 gallon into the 5 gallon bucket. Fill the 3 gallon bucket again and pour it into the 5 gallon bucket. You now have 4 gallons in the 5 gallon bucket.

Answer by Cuong Huy To for Generalization of the two bucket puzzle

2010-12-29T11:46:57Z

1. The problem

You are given two buckets of A and B volume units of water. Can you measure C volume units out of those two buckets (not using any other container).

Hint:

What are the values of C that there is a solution, or there is no solution.
What is the minimum number of steps to get C, if you know there exists a solution.
Find the algorithm to describe the solution.

2. Analysis of the general problem:

There will be no solution if C > A + B, or C is not divisible by gcd(A,B).
The solution when C = A + B is just straightforward.

3. Formal properties of the problem

a) (Property of C given (A,B)) : For any value of A and B, there exists a solution if-and-only-if C <= A+B and gcd(A,B) | C
b) (How to describe C given (A,B)) : If there exist a solution, then there exists a pair of natural numbers (x, y) so that C = Ax - By and C <= A+B.
c) (An easier way to know if there exists a solution) : If there exist a pair of natural numbers (x,y) such that C = Ax - By and C <= A+B, then there exist a solution to the problem

4. Proof of the above mentioned properties:

a) Other people in this thread have given the hint on how to prove this. You can prove yourself by using "proof by contradiction".
b) Straight forward if you look at the analysis part (part 2).
c) The following algorithm (in part 5) will make sure that it would output a solution with the smallest amount of steps.

5. Algorithms to generate the solution

b) Algorithm to find the pair (x,y)

[to be described here later]
c) Algorithm to generate a solution given the quintet of (A,B,C,x,y)

Algorithm: http://img585.imageshack.us/img585/4756/waterbucketgeleralalgor.png

6. Correctness of the algorithms

Hope that helps. Thanks