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:

  1. If the two beans are the same color, replace them with a white bean.
  2. 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.

Advertisements

2 thoughts on “The coffee bean puzzle

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s