Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Re: Challenge: N Jugs Problem

by blokhead (Monsignor)
on Apr 14, 2009 at 18:58 UTC ( #757463=note: print w/ replies, xml ) Need Help??


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:

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

blokhead


Comment on Re: Challenge: N Jugs Problem
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.

    Cheers - L~R

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://757463]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (6)
As of 2014-12-21 02:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (101 votes), past polls