in reply to Challenge: N Jugs Problem
In fact, the amounts which are possible are exactly the multiples of gcd(X,Y). Here's a proof: Since gcd(X,Y) divides both numbers, you'll see that all of the allowed operations preserve the invariant that each jug contains an amount which is divisible by gcd(X,Y). For the other direction, if you can get gcd(X,Y) into the big jug, then you can get c*gcd(X,Y) into the big jug, by repeating the same steps c times (of course this will be far from optimal, but it demonstrates that you can at least get this amount somehow). So it suffices to show that you can get gcd(X,Y). That part uses the fact that there exist integers a,b, such that aX + bY = gcd(X,Y), and uses a and b to determine how many times to fill the X and Y jugs. This argument should generalize easily to the more general problem you mentioned.
Update: elaboration on the above paragraph. Suppose aX + bY = gcd(X,Y). Then one of {a,b} is positive and one is nonpositive. Suppose a is positive. Then here is how you get gcd(X,Y) units in the Xunit jug:
 Do this "a" times: Fill the Xjug and dump as much as you can into the Yunit jug.
 If the Yjug fills during this step, and you have dumped the Yjug less than b times, then dump the Yjug on the ground and continue to empty the Xjug into the Yjug.
 Once you have dumped the Yjug b times, there will be aX  bY = aX + bY = gcd(X,Y) left in the Xjug, which you can pour into the target jug
</update>
BTW, the greedy approach won't necessarily work either. The greedy approach is (assuming X>Y): fill in increments of X as many times as you can, then fill in increments of Y as many times as you can, then somehow obtain the remaining amount to be filled, if any.
For instance, with X=5, Y=3, and target = 6, the best you can do is fill the 3unit jug twice. The greedy algorithm would first put 5 units in the target jug, then try to get 1 unit into the target jug, which will certainly take more steps.
In fact, if you restrict the target amount to something that is expressible as a positive linear combination of X and Y, you have an equivalent of the changemaking problem, where it is known that the greedy algorithm may not always work (for the generalized problem with more than 2 jugs/denominations).
Re^2: Challenge: N Jugs Problem by Limbic~Region (Chancellor) on Apr 14, 2009 at 19:14 UTC 
blokhead,
BTW, the greedy approach won't necessarily work either.
There is a reason I left that on my scratch and not in this post :) I knew if I said it was my hunch, I would immediately be proven wrong. Perhaps DP is the way to go.
 [reply] 
