It is a classical puzzle by Edsger Dijkstra. Not quoting the original problem but changing it into bag and balls, the puzzle is:
A bag contains some black and white balls. The following process is to be repeated as long as possible (assuming that we have infinite supply of black and white balls).
- Randomly select two balls from the bag. If they are the same color, throw them out, but put an extra black ball in.
- If they are different colors, place the white one back into the bag and throw the black one away.
As you can see that each iteration of the process reduces the number of balls in the bag by one. Also, repetition of the process must terminate with exactly one ball in the bag. The question is:
What, if anything, can be said about the color of the final ball based on the number of white balls and the number of black balls initially in the bag.
Answer
What can be said is that
the parity of the number of white balls never changes. Therefore, if there is an odd number of white balls initially then the last ball in the bag must be white; if an even number, the last ball must be black.
The way the puzzle is stated is, I think, deliberately unclear. You could equivalently (and more transparently) say: at each step you either remove one black ball, or remove two white and add one black. This also makes it a little more explicit that
at each step the parity of the number of black balls changes, which of course it must since you're removing one ball each time and the white parity is invariant.
(Of course the two statements aren't quite equivalent if for some reason you care about probabilities, since in the original version you remove two balls at random and let that determine which of the two things you do; but the puzzle itself is interested only in the worst case.)
No comments:
Post a Comment