aspose file tools*
The moose likes Programming Diversions and the fly likes [Easy]Coffee Can Problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "[Easy]Coffee Can Problem" Watch "[Easy]Coffee Can Problem" New topic
Author

[Easy]Coffee Can Problem

Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
This is again from Programming Pearls(Jon Bentely):
There is a CAN conaining some number of white beans and black beans.and there is a big vessel containing black beans only.You pick up two beans randomly from the CAN.If the beans are of same color then you throw both of them and add one black bean from vessel.If beans are of different color,you put white bean again in CAN and throw just black one.
1)Prove that this process terminates so that there will be only one bean left.
2)For which values of number of white/black beans ,there is only white bean left in the CAN at the end of process?
[ November 28, 2003: Message edited by: Capablanca Kepler ]

MH
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11314
    
  16

proof by induction... sort of...
clearly, if there is only one bean in the jar, we're done.
if there are two beans, then either they match or they dont. if they match, we get rid of both, and add one black bean from the vessel, leaving one bean.
if they don't match, we throw away the black, return the white, leaving one bean.
now, assume that if we have x beans left, we reduce to 1 bean. if we have x+ 1 beans, we can pick two, leaving x - 1 beans. either the two will match, or they won't. if they do, we throw them away, and add one black bean, leaving x in the can. we know this reduces to one bean.
if the two don't match, we throw the black one away, and return the white one, again leaving x beans in the can.
Q.E.D.
not sure about the second part yet, will have to think on it some more...


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

Joined: Dec 01, 2003
Posts: 226
can't you make that easier and just say that in each step the number of beans is reduced by 1?
Timmy Marks
Ranch Hand

Joined: Dec 01, 2003
Posts: 226
Odd number of white beans => white bean left at the end
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11314
    
  16

yeah, probably, but my Math background just sort of kicks in automatically, and makes me do formal analysis.
now i feel humbled...
as to part 2, since the whites can only be removed in pairs, i think if you start with an even number of whites, they'll all disappear, if you start with an odd, you'll end up with one leftover.
no formal proof this time, just gut reaction.
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
Originally posted by Timmy Marks:
Odd number of white beans => white bean left at the end

Yes, I think this is right answer for second part.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: [Easy]Coffee Can Problem