14
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Not directly related to your question, but I remember Nathaniel Dean math.txstate.edu/people/faculty/dean.html giving a talk at the Joint Math Meetings in '09 about undergraduate research problems, and one of them was about generalization of this puzzle (in particular to more than two buckets). So there's life in that old puzzle still! $\endgroup$
    – Thierry Zell
    Commented Dec 30, 2010 at 13:42
  • $\begingroup$ Stan Wagon posted a bucket-puzzle question to m.se, math.stackexchange.com/questions/1178368/… to which no one has posted anything by way of a solution. $\endgroup$
    – Gerry Myerson
    Commented Jul 17, 2017 at 13:04
  • $\begingroup$ A guide to the related literature are the references in vixra.org/abs/1509.0140 $\endgroup$
    – R. J. Mathar
    Commented Jul 24, 2023 at 11:55

5 Answers 5

Reset to default
23
$\begingroup$

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.)

Improve this answer
$\endgroup$
6
  • $\begingroup$ The problem was the less-than and greater-than signs. I changed them to \lt and \gt instead. $\endgroup$
    – Andrew Stacey
    Commented Nov 17, 2009 at 10:32
  • $\begingroup$ Ah--thank you very much, I will do that next time. I kept editing, though, and putting spaces in appears to have done the trick too. $\endgroup$
    – Elizabeth S. Q. Goodman
    Commented Nov 17, 2009 at 10:35
  • 1
    $\begingroup$ The problem is that the mathematics rendering is done last, even after it's been sent to the browser, so there's plenty of other things that muck around with the content first and the mathematics has to be safe-guarded from that. In particular, anything that looks remotely like an HTML tag will either get interpreted as such or removed by some zealous script. Putting a space after the opening sign means that it doesn't look like a tag any more so any compliant browser shouldn't misinterpret it. But there are plenty of non-compliant browsers out there so this isn't a stable solution. $\endgroup$
    – Andrew Stacey
    Commented Nov 17, 2009 at 10:53
  • $\begingroup$ Thanks for the great answer. Should it be $2B-(n-1)A$ instead of $2B-(n+1)A$? $\endgroup$
    – Shlomo Shamai
    Commented Nov 18, 2009 at 5:36
  • $\begingroup$ Thank you for accepting; I am glad to have seen the question. No, the way I wrote it works out--you have B in one bucket and B-nA in A before filling it, so you subtract B-(A-(B-nA))=B-((n+1)A-B). $\endgroup$
    – Elizabeth S. Q. Goodman
    Commented Nov 18, 2009 at 6:01
7
$\begingroup$

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

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

Improve this answer
$\endgroup$
6
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ What if you don't have that container? Is anything known about that? $\endgroup$
    – Andrew Stacey
    Commented Nov 17, 2009 at 9:45
4
$\begingroup$

Mathloger has a beautiful video about this, here.

Improve this answer
$\endgroup$
3
$\begingroup$

I am not a professional mathematician but a software developer given the generalization of this problem as a coding challenge. I implemented a simple site and open-sourced the code much to the help of this thread clarifying the equation so thought it would be a valuable addition.

My algorithm code can be seen at https://github.com/metame/infinite-lake/blob/master/app/js/algorithm.js.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .