You have a box with n red balls and n blue balls. You take out balls one by one at random until left only with balls of the same color. How many balls will be left (as a function of n)?
1) Roughly εn for some ε>0.
2) Roughly ?
3) Roughly log n?
4) Roughly a constant?
Here is the collective intuition regarding this problem
If you have two different boxes A with n red balls, and B with n blue balls and you take out at random with equal probabilities a ball from box A or a ball from box B, then when only one color is left the number of balls left is roughly . But in our case, when there are more red balls left it is more likely that we take out a red ball. Precisely, if we think about our problem but leaves the red and blue balls in different boxes, when there are a balls left in box A, and b balls left in box B you choose to take out another box from box A with probability a/(a+b). This seems to push the number of balls of each color closer together but by how much?
You can look at your drawing process as a random permutation of n red balls and n blue balls. We ask what is the distribution of the number of last balls of the same color. This is the same as the distribution D of the number of first balls of the same color. The first balls come at random with probability for red/blue very close to 1/2. This gives that the expected number of balls of the same color initial for the permutation is a constant, roughly 2, and that D is concentrated on constant numbers.
There were many interesting comments to this problem. Thanks for all the commentators! When Itai and Ronen asked me this question my spontaneous guess was wrong.