The process seems chaotic: each extraction depends on chance and the balls come and go. However, the final answer is completely deterministic from the first moment.
The last ball
Riddle statement
In an urn there are white and black balls.
You repeatedly draw two balls:
- if they are the same color, you remove them and put a black one;
- if they are a different color, you remove them and put a white one.
When there is only one ball left, what will its color depend on?
Show solution
Solution
Answer: the final color depends only on the initial parity of the number of white balls:
even initial white balls → last black ball;
odd initial white balls → last white ball.
The order of extraction has no influence at all.
Proof by invariant. We analyze how the number of white balls varies in each move:
two white → 2 white are removed and one black is added: the number of white changes by −2;
two black → no white is touched: the number of white does not change;
one white and one black → one white is removed and one white is added: the number of white does not change.
In all three cases, the parity of the number of white balls is preserved.
At the end there is only one ball left: if it is white, there is exactly 1 white ball (odd); If it is black, there are 0 white ones (even). The initial parity dictates which of the two cases is possible.