## Tuesday, April 17, 2012

### Color Balls

Non-Coding Problem:
Given a bag of n balls each with a different color. Each time you pick up a pair of balls and paint both to one of their colors. What's the expected number of steps before all balls become the same color?

Analysis:
This is a problem from the "Green Cover Book". It's easy to see that we have the following transition probability.
Thus if we let $$\mu_i$$ be the expected number of steps getting to one color when the bag has i distinct colors, then we have $\mu_i = 1 + \frac{i(i-1)}{n(n-1)} \mu_{i-1}+\left(1-\frac{i(i-1)}{n(n-1)}\right) \mu_i.$ From this we can use induction to prove that $\mu_i = \frac{i-1}{i} n(n-1).$ Therefore we have $\mu_n = (n-1)^2.$