Arjun Shastry

Ranch Hand

Posts: 1903

1

posted 13 years ago

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 ]

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

posted 13 years ago

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

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

Posts: 226

Timmy Marks

Ranch Hand

Posts: 226

posted 13 years ago
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

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.

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.