White and Black Balls in Urn. 1 in, 2 out. What Color Remains?

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

  1. if they are both black, one of them is put back and the other is thrown away,
  2. if one is black and the other white, the white one is put back and the black one is thrown away,
  3. 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?"

Solution


|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny

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

  1. if they are both black, one of them is put back and the other is thrown away,
  2. if one is black and the other white, the white one is put back and the black one is thrown away,
  3. 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.

(In a guise of interactive puzzle the problem appears elsewhere. In a probabilistic veil the problem has been discussed at Crux Mathematicorum)

References

  1. R. Honsberger, From Erdös To Kiev, MAA, 1996, pp 1-2
  2. J. G. McLoughlin et al, Jim Totten's Problems of the Week, World Scientific, 2013, #319

Related material
Read more...

  • A Three Pegs Question
  • Solitaire on a Circle
  • Peg Solitaire
  • The Game of Fif
  • Nim
  • Sums and Products
  • Splitting Piles
  • Chameleons of Three Colors
  • Moving Chips in Pairs Down a Checkerboard
  • Extension of Euclid's Game

  • |Contact| |Front page| |Contents| |Up|

    Copyright © 1996-2018 Alexander Bogomolny

    71471223