Return to Answer

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>A+B$. However, the following modification of the algorithm seems to work.

Let's assume $A < 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 < 2B-kA < 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.)

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

Edit: not all of this post is showing up, so I will edit it until it does.

Simon's answer points out that the Euclidean algorithm shows that gcd(A,B) divides C is necessary, but I the lack of large container makes the problem more difficult, because obviously you can't get C if $C\gt A+B$. So I think being as explicit as possible will help, if this answer is not too long-winded.

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 $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 the correct combination, 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$.

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>A+B$. However, the following modification of the algorithm seems to work.

Let's assume $A < 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 < 2B-kA < 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.)

Edit: not all of this post is showing up, so I will edit it until it does.

Simon's answer points out that the Euclidean algorithm shows that gcd(A,B) divides C is necessary, but I the lack of large container makes the problem more difficult, because obviously you can't get C if $C>A+B$. So I think being as explicit as possible will help, if this answer is not too long-winded.

Let's assume $A<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 $2B-kA<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 the correct combination, 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$.

Edit: not all of this post is showing up, so I will edit it until it does.

Simon's answer points out that the Euclidean algorithm shows that gcd(A,B) divides C is necessary, but I the lack of large container makes the problem more difficult, because obviously you can't get C if $C\gt A+B$. So I think being as explicit as possible will help, if this answer is not too long-winded.

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 $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 the correct combination, 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$.