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:

• Do this "a" times: Fill the X-jug and dump as much as you can into the Y-unit jug.
• If the Y-jug fills during this step, and you have dumped the Y-jug less than |b| times, then dump the Y-jug on the ground and continue to empty the X-jug into the Y-jug.
• Once you have dumped the Y-jug |b| times, there will be aX - |b|Y = aX + bY = gcd(X,Y) left in the X-jug, 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 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).

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.