Jan 20, 2009

You're given a coffe can contains Black, White beans and large pile of extra black beans. You then repeat the following process until there is a singl

You're given a coffe can contains Black, White beans and large pile of extra black beans. You then repeat the following process until there is a single bean left in the can.
Randomly select two beans from the can. If they're same color throw them both out and insert an extra black bean. If they're different colors return the white bean to the can and throw out the black.
Prove that process terminates. What can you say about the color of final remaining bean as function of the number of white and black beans originally in the can?
Process terminates as you reduce the amount by one at each step.
The parity of # of white beans does not change.
So if initially there were an odd number of white beans, the final bean will be white. Else the final bean will be black.

No comments:

Post a Comment