Generalization of the two bucket puzzle - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T06:58:10Z http://mathoverflow.net/feeds/question/5800 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/5800/generalization-of-the-two-bucket-puzzle Generalization of the two bucket puzzle Shlomo Shamai 2009-11-17T07:58:03Z 2010-12-30T13:08:35Z <p>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?"</p> <p>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?</p> http://mathoverflow.net/questions/5800/generalization-of-the-two-bucket-puzzle/5801#5801 Answer by Nick Salter for Generalization of the two bucket puzzle Nick Salter 2009-11-17T08:27:41Z 2009-11-17T08:27:41Z <p>Not an answer but rather a good thing to look at in connection with the problem-</p> <p><a href="http://numb3rs.wolfram.com/501/puzzle.html" rel="nofollow">http://numb3rs.wolfram.com/501/puzzle.html</a></p> http://mathoverflow.net/questions/5800/generalization-of-the-two-bucket-puzzle/5806#5806 Answer by Simon Wadsley for Generalization of the two bucket puzzle Simon Wadsley 2009-11-17T09:31:35Z 2009-11-17T09:31:35Z <p>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.</p> <p>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).</p> http://mathoverflow.net/questions/5800/generalization-of-the-two-bucket-puzzle/5807#5807 Answer by Elizabeth S. Q. Goodman for Generalization of the two bucket puzzle Elizabeth S. Q. Goodman 2009-11-17T10:24:59Z 2009-11-17T10:55:18Z <p>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.</p> <p>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$. </p> <p>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$). </p> <p>(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.)</p> http://mathoverflow.net/questions/5800/generalization-of-the-two-bucket-puzzle/22730#22730 Answer by Bob for Generalization of the two bucket puzzle Bob 2010-04-27T15:11:58Z 2010-04-27T15:11:58Z <p>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.</p> http://mathoverflow.net/questions/5800/generalization-of-the-two-bucket-puzzle/50647#50647 Answer by Cuong Huy To for Generalization of the two bucket puzzle Cuong Huy To 2010-12-29T11:46:57Z 2010-12-30T13:08:35Z <h2>1. The problem</h2> <p>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).</p> <p>Hint:</p> <ul> <li>What are the values of C that there is a solution, or there is no solution.</li> <li>What is the minimum number of steps to get C, if you know there exists a solution.</li> <li>Find the algorithm to describe the solution.</li> </ul> <h2>2. Analysis of the general problem:</h2> <ul> <li>There will be no solution if <em>C > A + B</em>, or C is not divisible by <em>gcd(A,B)</em>.</li> <li>The solution when <em>C = A + B</em> is just straightforward.</li> </ul> <h2>3. Formal properties of the problem</h2> <ul> <li>a) <em>(Property of C given (A,B))</em> : For any value of A and B, there exists a solution if-and-only-if <em>C &lt;= A+B</em> and <em>gcd(A,B) | C</em> </li> <li>b) <em>(How to describe C given (A,B))</em> : If there exist a solution, then there exists a pair of natural numbers (x, y) so that <em>C = Ax - By</em> and <em>C &lt;= A+B</em>.</li> <li>c) <em>(An easier way to know if there exists a solution)</em> : If there exist a pair of natural numbers (x,y) such that <em>C = Ax - By</em> and <em>C &lt;= A+B</em>, then there exist a solution to the problem</li> </ul> <h2>4. Proof of the above mentioned properties:</h2> <ul> <li>a) Other people in this thread have given the hint on how to prove this. You can prove yourself by using "proof by contradiction".</li> <li>b) Straight forward if you look at the analysis part (part 2).</li> <li>c) The following algorithm (in part 5) will make sure that it would output a solution with the smallest amount of steps.</li> </ul> <h2>5. Algorithms to generate the solution</h2> <ul> <li><p>b) Algorithm to find the pair (x,y)</p> <p><em>[to be described here later]</em></p></li> <li><p>c) Algorithm to generate a solution given the quintet of (A,B,C,x,y)</p> <p>Algorithm: <a href="http://img585.imageshack.us/img585/4756/waterbucketgeleralalgor.png" rel="nofollow">http://img585.imageshack.us/img585/4756/waterbucketgeleralalgor.png</a></p></li> </ul> <h2>6. Correctness of the algorithms</h2> <p>Hope that helps. Thanks</p>