A Classic Programming Riddle from David Gries' "Science of Programming"

I've recently been re-reading one of my favorite programming book, The Science of Programming by David Gries.

In the introduction to the last part of the book Gries presents a riddle that is an amazing, compact example of the kind of thinking that good computer programmers use.

The Riddle

A coffee can contains some black beans and some white beans. The following process is to be repeated as long as possible.

Randomly select two beans from the can. If they have the same color, throw them out, but put another black bean in. (Enough extra black beans area available to do this.) If they are different colors, place the white one back into the can and throw the black one away.

Execution of this process reduces the number of beans in the can by one. Repetition of the process must terminate with exactly one bean in the can, for then two beans cannot be selected. The question is: what, if anything, can be said about the color of the final bean based on the number of white beans and the number of black beans initially in the can?

As Gries observes in the book, you can waste hours playing out different possible scenarios without seeing an interesting pattern. A different way of thinking that allows you to reason about every possible starting configuration, and every possible sequence of draws of beans is needed.

The Solution

Lets look at what combinations of 2 beans can be drawn, and what happens to the number of beans of each color in the can:

  1. Both black: In this case both beans are the same color, so both are thrown away and a new black bean is placed in. The number of white beans in the can does not change, and the number of black beans in the can decreases by 1
  2. One black and one white: The black bean is thrown away and the white one is put back in the can. The number of white beans does not change, and the number of black beans decreases by 1
  3. Both white: Both beans are thrown away and a new black bean is placed in. The number of white beans in the can decreases by 2 and the number of black beans in the can increases by 1

More succinctly:

  1. Both black: Black -1, White -0
  2. One white one black: Black -1, White -0
  3. Both white: Black -0, White -2

Now ignore the changes in the number of black beans:

  1. Both black: White -0
  2. One white one black: White -0
  3. Both white: White -2

So the number of white beans after each selection is either the same as before, or is 2 less than before. Now 2 more observations will lead us to the solution to the riddle:

  1. An even number minus 2 is always another even number, 8 - 2 = 6, 6 - 2 = 4, etc.
  2. An odd number minus 2 is always another odd number, 9 - 2 = 7, 7 - 2 = 5, 5 - 2 = 3, etc.

Looking at observation (1.) we can see that if the initial number of white beans in the can is even the final number of white beans in the can must be even, because after each draw the number of white beans is either the same as it was before, or has decreased by 2. Similarly if the initial number of white beans is odd the final number must be odd because of (2.).

Now lets apply this thinking to a concrete case. Suppose initially there are 882 white beans in the jar. 882 is an even number, so the number of white beans in the jar will always be even. Therefore, when there is only one bean left in the jar that bean must be black, because if it weren't there would be exactly one white bean in the jar, and 1 is an odd number!

Conversely, suppose there are 881 white beans in the jar to begin with. Then the number of white beans in the jar is always odd, so when exactly one bean is left it must be white, because if the only remaining bean were black there would be 0 white beans in the jar, and 0 is an even number.

Amazingly, knowing the number of white and black beans in the can initially is actually too much information. The solution is simply that if the number of white beans is initially even then the last bean in the jar will be black, and if the number of white beans is initially odd then the last bean in the jar will be white.

Leave a Reply

Your email address will not be published. Required fields are marked *