A box contains n balls, each colored uniquely. You pick two balls from the box, both uniformly (at random), and you paint the second ball the color of the first. Then you put both balls back into the box. What is the expected number of times this needs to be done so that all balls in the box have th

I think I've calculated this for n from 1 to 4, and I get [math](n-1)^2[/math] in each case. No idea yet whether this generalizes or why. It's a lovely problem, though. But here's a sketch of how I did it for [math]n=4[/math], in case it might inspire someone. (The cases when [math]n=1,2,3[/math] are much simpler.) I use the phrase "the 2-1-1 state" to refer to the state in which there are two balls of one color, one of another color, and one of a third color. Similarly, the "3-1 state" is when there are three of one color and one of a third color; and the "2-2 state" is when there are two of two different colors. Let [math]t_{211}, t_{31}, t_{22}[/math] denote respectively the expected number of times left once we get two the 2-1-1, 3-1, or 2-2 states. From the 2-1-1 state, there's a 1/2 chance of returning to the 2-1-1 state, a 1/3 chance of going to the 3-1 state, and a 1/6 chance of going to the 2-2 state. So, [math]t_{211} = 1 + t_{211}/2 + t_{31}/3 + t_{22}/6[/math]. Likewise, [math]t_{31} = 1 + t_{31}/2 + t_{22}/4 + 0/4[/math], with the [math]0/4[/math] term representing the fact that there's a 1/4 chance that the game ends on this next turn. And, [math]t_{22} = 1 + t_{31} \cdot 2/3 + t_{22}/3[/math]. Solving these three equations gives [math](t_{211},t_{31},t_{22}) = (8,5.5,7)[/math]. Since the first move always produces a 2-1-1 state, the expected number of terms from the beginning is [math]1+t_{211} = 9[/math].