File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Programming Diversions and the fly likes Two  bucket puzzle Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Two  bucket puzzle" Watch "Two  bucket puzzle" New topic
Author

Two bucket puzzle

rehans oberoi
Ranch Hand

Joined: Dec 06, 2005
Posts: 174
If you have two buckets, one with red paint and the other with blue paint, and you take one cup from the blue bucket and pour it into the red bucket. Then you take one cup from the red bucket and pour it into the blue bucket. Which bucket has the highest ratio between red and blue? Prove it mathematically.
David O'Meara
Rancher

Joined: Mar 06, 2001
Posts: 13459

They are the same, 2=2
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1007
    
    3
Assuming perfect mixing...
----
Scenario 1: Let's say each started with nine cups of pure paint.

Start: 9 c of (100% red) <--> 9 c (100% blue)
After one move: 10 c of (90%red/10%blue) <--> 8 c of (100% blue)
Partway through second move: 9 c of (90%red/10%blue) <--> 1 c of (90%red/10%blue) <--> 8 c of (100% blue)
After second move: 10 c of (90%red/10%blue) <--> 9 c of (91.1% blue/8.9%red)

So... the original blue bucket has paint that is more disproportionately mixed.

----
Scenario 1: Let's say each started with one cup of pure paint.

Start: 1 c of (100% red) <--> 1 c (100% blue)
After one move: 2 c of (50%red/50%blue) <--> 0 c of (anything)
Partway through second move: 1 c of (50%red/50%blue) <--> 1 c of (50%red/50%blue) <--> 0 c of (anything)
After second move: 1 c of (50%red/50%blue) <--> 1 c of (50% blue/50%red)

So... both buckets have the same color paint.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11312
    
  16

actually, the buckets don't even have to be "perfectly mixed", or mixed at all - assuming both start and end with the same amount. i don't think you even need to have the same amount in the blue and red bucket originally.

the blue bucket originally contains pure blue paint. you dump in some red, mix it a little or a lot, it doesn't matter. you take out some amount of paint from this, and dump it into the red bucket, returning both paint buckets to their original volume.

there is now X red paint in the originally blue bucket. that means that the originally red bucket is missing X paint. in order for the red bucket to be back at it's original volume, that much must restored to it. it MUST be replaced by the blue paint.
[ March 09, 2006: Message edited by: fred rosenberger ]

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1007
    
    3
Originally posted by fred rosenberger:
actually, the buckets don't even have to be "perfectly mixed", or mixed at all - assuming both start and end with the same amount. i don't think you even need to have the same amount in the blue and red bucket originally.


Agreed. I just picked that assumption and starting condition so that I had SOME numbers to work with.


the blue bucket originally contains pure blue paint. you dump in some red, mix it a little or a lot, it doesn't matter. you take out some amount of paint from this, and dump it into the red bucket, returning both paint buckets to their original volume.

there is now X red paint in the originally blue bucket. that means that the originally red bucket is missing X paint. in order for the red bucket to be back at it's original volume, that much must restored to it. it MUST be replaced by the blue paint.


So are you saying the ratios of paint colors inthe two buckets are equal (but opposite) at the end?
Jayesh Lalwani
Ranch Hand

Joined: Nov 05, 2004
Posts: 502
Originally posted by fred rosenberger:


there is now X red paint in the originally blue bucket. that means that the originally red bucket is missing X paint. in order for the red bucket to be back at it's original volume, that much must restored to it. it MUST be replaced by the blue paint.

[ March 09, 2006: Message edited by: fred rosenberger ]



If you mix the paint in the blue bucket before transferring X paint to the red bucket, some percentage of the X paint going into the red bucket will be red and some will be blue. However, if you don't mix the blue paint before the transfer, then you don't know how much of the red paint is going into the red bucket

That's why it matters if you mix the paint or not.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11312
    
  16

That's why it matters if you mix the paint or not.


i think you're wrong. let's talk percentages. originally, the blue bucket has a volume of 100%. we then dump in an unknown amount of red. this gives the blue bucket some amount greater than 100%. but now we need to reduce it back down, so we scoop some out. we are back at 100%, but now we have some volume X% of blue paint, and some volume 100 - X% of red paint. In other words, SOME amount of red paint has replaced an EQUAL volume of blue paint in the blue bucket.

where did that blue paint go? into the red. it doesn't matter if you mix or not, because in the end, the blue bucket has the same total amount of paint as when it started. HOWEVER much red is in it is how much blue paint is in the red bucket.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
The original question was, which bucket has a higher ratio of red to blue?

For this entire post, I will assume no mixing, or imperfect mixing.

After the two transfers, the red bucket will ultimately lose 0-1 cups of red, and gain 0-1 cups of blue in its place. And the blue bucket will lose 0-1 cups of blue, and gain 0-1 cups of red.

If we also assume that both buckets had more than two cups initially, then we can guarantee that whatever the exact ratio, the red bucket now has more than one cup of red, and at most one cup of blue. Therefore the red bucket is more than 50% red. And the blue bucket would have at most one cup of red, and more than one cup of blue. Therefore the red bucket has a higher ratio of red to blue than the blue bucket has. Remember, that's what the question actually asked.

Note that I have not assumed that the two volumes were the same initially - I just assumed they were both greater than two cups. If that's the case, the red bucket has more red. Period.

If the two buckets did not have more than two cups initially, then it becomes possible for the blue bucket to end up with more red. For example, start with 1.9 cups in each. With no mixing, we could end with the red bucket containing 0.9 red and 1.0 blue, and the blue bucket containing 1.0 red and 0.9 blue. Thus the blue bucket would end up with a higher concentration of red.

It's possible to write equations establishing exactly what the concentrations of each would be, in terms of the initial volumes and the amount exchanged. But without further assumptions, they don't seem to lead anywhere interesting, so I'll skip that for now. Too much work to write, without a good payoff at the end. I'll just assert that if we allow either initial volume to be less than 2 cups, it's possible for either bucket to end up with a higher concentration of red than the other one. Depending on how they're mixed.
[ March 10, 2006: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, Twister
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
And for this post, I will assume perfect mixing.

Let the initial volume of red paint be R, and the volume of blue is B.

After the first transfer we have:

    red bucket: R-1 red, 0 blue

    blue bucket: 1 red, B blue

Now mix the blue bucket evenly and extract 1 cup. This cup will contain 1/(B+1) red, and B/(B+1) blue. Transfer this to the red bucket, and we have:

    red bucket: R - 1 + 1/(B+1) red, B/(B+1) blue

    blue bucket: 1 - 1/(B+1) red, B - B/(B+1) blue

which simplify to:

    red bucket: (RB+R-B)/(B+1) red, B/(B+1) blue

    blue bucket: B/(B+1) red, B^2/(B+1) blue

Let's call the red-to-blue ratios for the red and blue buckets P and Q, respectively. We get:

    P = (RB+R-B)/B

    Q = 1/B

Which is bigger? Let's calculate the difference:

    P - Q = (RB+R-B-1)/B = (R-1)(B+1)/B

Remember that we initially took 1 full cup from the red bucket, so it must be true that R >= 1. Which means that one of two things is true:
  • R=1, and P-Q=0, so the two ratios are exactly equal
  • R > 1, and P-Q > 0 (all factors are positive), so P > Q
  • So, with perfect mixing, the red bucket will always end up with a higher concentration of red unless its initial volume was exactly one cup - in which case the concentrations of both buckets are equal.

    Ryan noted in his first post that equal concentrations were possible - except he assumed that both buckets had one cup. Turns out it doesn't matter how big the blue bucket is; only the red bucket matters. If R=1, the concentrations will be equal. For all other cases, the red bucket ends up with a higher ratio of red.
    Stan James
    (instanceof Sidekick)
    Ranch Hand

    Joined: Jan 29, 2003
    Posts: 8791
    Some amount of red paint is in the blue can. To make room for it, the same amount of blue has to be in the red can.

    The sizes of the cans don't matter. The same cup volume is moved both ways, both levels are back where they started.
    [ March 12, 2006: Message edited by: Stan James ]

    A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
    Jim Yingst
    Wanderer
    Sheriff

    Joined: Jan 30, 2000
    Posts: 18671
    Yup. But the question was, which bucket has the highest ratio between red and blue? It's good to know that the final volumes of paint in each bucket equal the initial volumes, and that the amount of blue paint in the red bucket equals the amount of red paint in the blue bucket. Great. But which ends up with a higher ratio of red to blue?
    Ryan McGuire
    Ranch Hand

    Joined: Feb 18, 2005
    Posts: 1007
        
        3
    Originally posted by Jim Yingst:
    Yup. But the question was, which bucket has the highest ratio between red and blue? It's good to know that the final volumes of paint in each bucket equal the initial volumes, and that the amount of blue paint in the red bucket equals the amount of red paint in the blue bucket. Great. But which ends up with a higher ratio of red to blue?


    Hmmm... I interpreted the question to be which bucket had the most disproportionate mixture. To me "highest ratio between red and blue" is not the same as "highest ratio of red to blue". The difference is that the first phrase doesn't specify the order of the ratio.

    I feel the same way about the word "difference". Which is greater: the difference between 2 and 5 or the difference between 10 and 1? I say that's a comparison between 3 and 9. Other's would say it's between 3 and -9. The same applies here.

    Obviously, if the original paint cans contain significantly more than one cup, then the original red can will still have more red.

    BUT... will the original red can have more red paint than the original blue can has blue?

    And now I'm embarassed to say that my math was wrong the first time I worked this out.

    What I should have written:
    Start: 9 c of (100% red) <--> 9 c (100% blue)
    After one move: 10 c of (90%red/10%blue) <--> 8 c of (100% blue)
    Partway through second move: 9 c of (90%red/10%blue) <--> 1 c of (90%red/10%blue) <--> 8 c of (100% blue)
    After second move: 9 c of (90%red/10%blue) <--> 9 c of (90% blue/10%red)

    So both buckets end up 90/10. I would say they have "equally disproportionate proportions."

    As Mr. James pointed out, this result makes sense. Whatever amount of blue paint there is in the red can, there must be the same amount of red paint in the blue can. You could swap paint back and forth in various amount all day. If they end up with the same volumes, then the proportions of paint must be equal (but opposite).
    [ March 21, 2006: Message edited by: Ryan McGuire ]
    fred rosenberger
    lowercase baba
    Bartender

    Joined: Oct 02, 2003
    Posts: 11312
        
      16

    what happens if the two buckets don't start with the same volume? maybe the blue bucket holds 10 cups, and the red holds 2 cups. we move 1 cup of red to the blue, then 1 cup of blue-and-red back to the red.

    for simplicity sake, say we end up with 1/2 cup of blue in the red, and 1/2 cup of red in the blue. we now have a 19-to-1 ratio of blue to red in the blue bucket, but a 3-to-1 ratio in the red bucket.

    while the volume of blue-in-the-red will equal the red-in-the-blue, your ratios are not equal but opposite.
    Jim Yingst
    Wanderer
    Sheriff

    Joined: Jan 30, 2000
    Posts: 18671
    [Ryan]: To me "highest ratio between red and blue" is not the same as "highest ratio of red to blue". The difference is that the first phrase doesn't specify the order of the ratio.

    I would say that "ratio between red and blue" is a bit more ambiguous than "ratio of red to blue". I still think it's more suggestive of R/B than it is to B/R. Even if one assumes that the two are both possible interpretations, how does one get to this idea that it means R/B for one bucket, and B/R for the other? It's a mystery to me. But this (reversing the ratios) does seem to be the question that most people herewant to answer. Is it because the answer to that question is ultimately very simple? Is that the appeal? That's my guess. I just don't see it in the original language of the problem. Not that the answer to any version of this problem is terribly complex - the only reason this thread has gone on so long is that the initial problem left too many things unstated or poorly stated, so we've got a mess of different possible interpretations. Most of which have dead-horse solutions at this point, I think.
    Mark Spritzler
    ranger
    Sheriff

    Joined: Feb 05, 2001
    Posts: 17250
        
        6

    What if there's a hole in the buckets?

    Mark


    Perfect World Programming, LLC - Two Laptop Bag - Tube Organizer
    How to Ask Questions the Smart Way FAQ
    fred rosenberger
    lowercase baba
    Bartender

    Joined: Oct 02, 2003
    Posts: 11312
        
      16

    is there only one hole in one bucket, or does each bucket have it's own unique hole?
    Srinivasa Raghavan
    Ranch Hand

    Joined: Sep 28, 2004
    Posts: 1228
    Originally posted by Mark Spritzler:
    What if there's a hole in the buckets?

    Mark


    What if there is hole in the cup ?


    Thanks & regards, Srini
    MCP, SCJP-1.4, NCFM (Financial Markets), Oracle 9i - SQL ( 1Z0-007 ), ITIL Certified
    Stan James
    (instanceof Sidekick)
    Ranch Hand

    Joined: Jan 29, 2003
    Posts: 8791
    The smaller bucket has the higher ratio of the other color to the original color.

    Re hole in the bucket: My dad taught college math for 36 years. When I was in about 6th grade he punched a nail hole in a soup can and computed how long it would take for a full can of water to drain. It was several sheets of yellow legal pad as I recall, and I was bored to tears. We finally ran the experiment and his prediction was extremely close. I was impressed, but not enough that I didn't major in music.
    Rakesh Joshi
    Ranch Hand

    Joined: Feb 24, 2006
    Posts: 218
    Assume that each bucket have 100 ML of Paint
    Actual Paint = AP
    Cap = C
    B1 = 100 ML
    B2 = 100 ML

    Now we have a Cup which is keep 10 ML of paint.

    AP = (B1 B2) - C
    APB1 = 100 ML � 10 ML
    APB1 = 90 ML
    APB2 = 110 ML

    APB2 = 110 ML � 10 ML
    APB2 = 100 ML
    APB1 = 100 ML

    APB1 = APB2
    100 ML = 100 ML
    The Ratio = 1:1


    Life is a Game play it.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Two bucket puzzle