http://www.perlmonks.org?node_id=757463


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 non-positive. Suppose a is positive. Then here is how you get gcd(X,Y) units in the X-unit 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 3-unit 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 change-making problem, where it is known that the greedy algorithm may not always work (for the generalized problem with more than 2 jugs/denominations).

blokhead