The coffee bean puzzle
There is a puzzle listed at http://www.cs.cmu.edu/~mblum/research/pdf/grad.html that goes as follows:
Given a can of black and white coffee beans, do the following: Pull out two beans: if both are the same color, replace them with a white bean. If the two are different, replace them with a black bean. What color is the last bean?
I thought about it for a while and figured out the answer, but I was unsatisfied with the way the puzzle is phrased, because there isn’t one set answer: from the information given the last bean cannot be said to be either black or white. Instead, the answer is a simple method of determining the color of the last bean, given additional information. This discrepancy led me to waste some time trying to find a determinative answer first, and then to question whether I really had the correct answer once I had found it. But just giving the requisite information in addition to the above description gives too much of a hint, and collapses the puzzle to a much simpler one. So I would phrase the puzzle like this:
Given a can of black and white coffee beans, you are allowed to do the following operation repeatedly. Pull out two beans, then:
- If the two beans are the same color, replace them with a white bean.
- If the two beans are different, replace them with a black bean.
What simple method can you use to know what the color of the last bean will be?
Now it’s clear that there is no set answer, but hopefully I haven’t given away too much. The answer will be in a separate post.
To keep the spoilers out of here, I’ve given an informal proof of the answer over at reddit:
http://www.reddit.com/r/puzzles/comments/9noxo/the_coffee_bean_puzzle/c0djfy8
The answer was no immediately obvious, though after writing down the outcomes a few levels deep the pattern emerged and I just had to figure out why.