October 31, 2007

In a large urn there are 1999 orange balls and 2000 yellow balls. Next to the urn is a large pile of yellow balls. The following procedure is performed repeatedly.

Two balls are chosen at random from the urn:

If both are yellow, one is put back, the other thrown away;
If both are orange, they are both thrown away and a yellow ball from the pile is put into the urn;
If they are of different colors, the orange one is put back into the urn and the yellow one is thrown away.

What is the color of the last ball in the urn?

Solution. The key observation is that the procedure never alters the parity (even/odd) of the orange balls. Each performance results in a loss of one ball from the urn, so that eventually, just one is left. Its color must be orange since the original number of such balls is odd.