[Easy]Coffee Can Problem

[Arjun Shastry]

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 ]

[fred rosenberger]

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

[Timmy Marks]

can't you make that easier and just say that in each step the number of beans is reduced by 1?

[Timmy Marks]

Odd number of white beans => white bean left at the end

[fred rosenberger]

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]

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.