In a large urn there are 75 white balls and 150 black ones, and beside the urn is a big pile of black balls. Now, the following two-step operation is performed repeatedly. First, two balls are withdrawn at random from the urn and then
- if they are both black, one of them is put back and the other is thrown away,
- if one is black and the other white, the white one is put back and the black one is thrown away,
- if they are both white, they are both thrown away and a black ball from the pile is put into the urn.
Therefore, whatever the case, at each stage two balls removed from the urn and one is put back, thus reducing the number of balls in the urn by one. Eventually, then, the urn will reach the point of containing just a single ball. The question is "What color is this last ball?"
In a large urn there are 75 white balls and 150 black ones, and beside the urn is a big pile of black balls. Now, the following two-step operation is performed repeatedly. First, two balls are withdrawn at random from the urn and then
- if they are both black, one of them is put back and the other is thrown away,
- if one is black and the other white, the white one is put back and the black one is thrown away,
- if they are both white, they are both thrown away and a black ball from the pile is put into the urn.
Therefore, whatever the case, at each stage two balls removed from the urn and one is put back, thus reducing the number of balls in the urn by one. Eventually, then, the urn will reach the point of containing just a single ball. The question is "What color is this last ball?"
The effect of the two-step operation is to reduce the total number of balls in the urn by one. Obviously, so. But there is a more subtle observation. The number of white balls either does not change at all or drops by two; the number of black balls is either decreased by one or is increased by 1. Looking at the number of white balls we observe that
The number of white balls preserves its parity throughout the process.
In other words, the parity of the number of white balls is an invariant of the process. Since at the beginning the number of white balls is odd, it is going to remain odd, meaning that the white balls can't vanish from the urn. When only one ball remains, it is bound to be white.
On the other hand, had we started with an even number of white balls, it would be impossible to end up with one (an odd number) of white balls, so that the remaining ball would be necessarily black.
References
- R. Honsberger, From Erdös To Kiev, MAA, 1996, pp 1-2
