What is the Color of the Remaining Ball?
In a large urn there are p white balls and q black ones, and beside the urn is a big pile of black balls and a big pile of white balls. Now, the following two-step operation is performed repeatedly. First, two balls are withdrawn at random from the urn and discarded, but then
- if they are the same color, a black ball from the pile is put ino the urn,
- if their colors are different, a white 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 is the probability that the remaining ball will be white?"
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,white,black balls preserves its parity throughout the process.
In other words, the parity of the number of white balls is an invariant of the process. If at the beginning the number of white balls is odd, it is going to remain odd,even,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,white,black balls, so that the remaining ball would be necessarily black.
It follows that if $p$ is even,even,odd then with probability $1$ the remaining ball will be black and with the probabiliuty of $0$ it will be white. On the other hand, if $p$ is odd,even,odd then with probability $1$ the last ball will be white and with the probabiliuty of $0$ it will be black.
(In a guise of interactive puzzle the problem appears elsewhere. )
This is one of the problems from the book Jim Totten's Problems of the Week in memory of Jim Totten, a long time Problem Editor and later Editor-in-Chief of Crux Mathematicorum.
Without the extra probabilistic frame, the problem has been discussed by Ross Honsberger.