Well, for containers of x and y capacity, the only numbers that can be formed are of the form
k*gcd(x,y) <= x+y (you can't get more than filling up the two containers to the brim)
where k is a positive integer.
This can be shown by noting that you should only fill the large one when it's empty and empty the small one when it's full (and pour from the large into the small). Then, assuming that x>y (without loss of generality), the number of times we fill up the x container and empty out the y container is given by the expression:
ax-by=d < x+y
where a and b are non-negative integers. Note that the gcd(a,b) must divide ax-by, so it must also divide d. Therefore, d is a multiple of gcd(a,b) as well.
General way of solving for a certain number of liters (containers of X,y: X>y (X=y is stupid)):
1. Fill X.
2. Pour X into y.
3. Empty y if it's full.
4. Repeat 2-3 until there's nothing left in X.
5. Repeat 1-4 until you get your desired amount.
The Euclidean algorithm is how you figure out how many times you'll fill X and empty y. Check out this example: Containers of size 87 and 5, making a desired amount of 3.
a = b*c + d
b = d*e + f
d = f*g + h
...
87 = 5*17 + 2
5 = 2*2 + 1
2 = 2*1 + 0
Now, since the last equation leaves no remainder, the right-most term on the previous line is the gcd(87,5): gcd(87,5) = 1
Now, let's look at the equation:
5 = 2*2 + 1, leads to:
1 = 5 - 2*2
1 = 5 - 2*(87 - 5*17)
1 = 35*(5) - 2*(87)
3 = 105*(5) - 6*(87)
Oh darn, I swapped it around. Whatever. This is just the opposite of my solution: filling up the smaller one and pouring it into the larger one until it's full. For this, you fill up the 5 container 105 times and empty the 87 container 6 times.
A particular solution to the diophantine equation 5x + 87y = 3 is (x,y) = (105,-6). The general solution is: (105 + 87/gcd(87,5)t,-6 - 5/gcd(87,5)t) where t is an integer. Then, we can choose t = -2 to get a solution of (-69,4). This would mean we fill up the 87 container 4 times and empty out the 5 container 69 (lulz) times.
Ugh, this is ugly, ask for clarification if you don't understand.
most likely by the Anicent Chinese who did so much work with modular arithmetic and number theory.
I'm Chinese, but by no means Ancient.
