A balls-and-colours problem A box contains n balls coloured 1 to n. Each time you pick two balls from the bin - the first ball and the second ball, both uniformly at random and you paint the second ball with the colour 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 the same colour?
Answer (Spoiler put through rot13.com): Gur fdhner bs gur dhnagvgl gung vf bar yrff guna a.
Someone asked me this puzzle some four years back. I thought about it on and off but I have not been able to solve it. I was told the answer though and I suspect there may be an elegant solution.
Thanks.
 A: This answer is inspired by JBL's comment on Aaron's answer:
Fix $n$, so that I don't have to include it in my notation. In all other respects, copy Aaron's notation. JBL observes that there appear to be numbers $f(1)$, $f(2)$, ..., $f(n-1)$ such that 
$$ p_{\lambda} = \sum_{k \in \lambda} f(k). \quad \quad (*)$$
We will show that such $f$'s exist, and give formulas for them. In particular, it will be clear that $f(1) = (n-1)^2/n$, proving the result. For convenience, we set $f(0)=f(n)=0$.

It seems best to describe the $f$'s by the following relation
$$ \frac{k}{n} = \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right) \ \mbox{for} \ 1 \leq k \leq n-1 \quad \quad (**)$$
Our proof breaks into two parts: showing that there is a unique solution to $(**)$ and showing that the resulting $f$'s obey $(*)$. We do the second part first.

We must establish the Markov relation:
$$\sum_{k \in \lambda} f(k) = 1 + \sum_{\mu} p(\lambda \to \mu) \sum_{k \in \mu} f(k).$$
For any $k$ in $\lambda$, the modified partition $\mu$ contains either $k-1$, $k+1$ or $k$, depending on whether we lost a ball of the corresponding color, gained one, or kept the same number. 
The probabilities of these events are $k(n-k)/n(n-1)$, $k(n-k)/n(n-1)$, and $1-2 k(n-k)/n(n-1)$, respectively. 
So we must show that
$$\sum_{k \in \lambda} f(k) = 1 + \sum_{k \in \lambda} \left( \frac{k(n-k)}{n(n-1)} f(k-1) + \left( 1- \frac{2k(n-k)}{n(n-1)} f(k) \right) + \frac{k(n-k)}{n(n-1)} f(k+1)\right).$$
Canceling $\sum_{k \in \lambda} f(k)$ from both sides, we must show that
$$0 = 1 - \sum_{k \in \lambda} \frac{k(n-k)}{n(n-1)} \left( - f(k-1) + 2 f(k) - f(k+1) \right). $$
By $(**)$, the defining equation of the $f$'s, this is
$$1- \sum_{k \in \lambda} (k/n) = 1 - |\lambda|/n=0$$~
as desired.
So, if we can find $f$'s obeying $(**)$, we will have $(*)$.

Let $g_j$ be the length $(n-1)$ vector
$$( n-j, 2(n-j), 3(n-j), \ldots, j(n-j), \ldots, 3j, 2j, j)$$
The key feature of $g_j$ is that 
$$- g_j(k-1) + 2 g_j(k) - g_j(k+1) = \begin{cases} n \quad k=j \\ 0 \quad k \neq j \end{cases}$$
where we set $g_j(0)=g_j(n)=0$.
Let $f$ be the vector $(f(1), f(2), \ldots, f(n-1))$. 
Rewrite $(**)$ as
$$ \frac{n-1}{n-k} = - f(k-1) + 2 f(k) - f(k+1).$$
So we see that 
$$f = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} g_k$$
In particular, 
$$f(1) = \sum_{k=1}^{n-1} \frac{n-1}{n(n-k)} (n-k) = \frac{(n-1)^2}{n}$$
as desired. More generally,
$$f(j) = \sum_{k=1}^{j-1} \frac{n-1}{n(n-k)} k(n-j) +  \sum_{k=j}^{n-1} \frac{n-1}{n(n-k)} j(n-k) = \frac{(n-1)(n-j)}{n} \sum_{k=1}^{j-1} \frac{k}{n-k} + \frac{j(n-j)(n-1)}{n}.$$

A: It can probably be done by looking at the sum of squares of sizes of color clusters and then constructing an appropriate martingale. But here's a somewhat elegant solution: reverse the time!
Let's formulate the question like that. Let $F$ be the set of functions from $\{1,\ldots,n\}$ to $\{1,\ldots,n\}$ that are almost identity, i.e., $f(i)=i$ except for a single value $j$. Then if $f_t$ is a sequence of i.i.d. uniformly from $F$, and
$$g_t=f_1 \circ f_2 \circ \ldots \circ f_t$$
then you can define $\tau= \min \{ t | g_t \verb"is constant"\}$. The question is then to calculate $\mathbb{E}(\tau)$.
Now, one can also define the sequence
$$h_t=f_t \circ f_{t-1} \circ \ldots \circ f_1$$
That is, the difference is that while $g_{t+1}=g_t \circ f_{t+1}$, here we have $h_{t+1}=f_{t+1} \circ h_t$. This is the time reversal of the original process.
Obviously, $h_t$ and $g_t$ have the same distribution so
$$\mathbb{P}(h_t \verb"is constant")=\mathbb{P}(g_t \verb"is constant")$$
and so if we define $\sigma=\min \{ t | h_t \verb"is constant"\}$ then $\sigma$ and $\tau$ have the same distribution and in particular the same expectation.
Now calculating the expectation of $\sigma$ is straightforward: if the range of $h_t$ has $k$ distinct values, then with probability $k(k-1)/n(n-1)$ this number decreases by 1 and otherwise it stays the same. Hence $\sigma$ is the sum of geometric distributions with parameters $k(k-1)/n(n-1)$ and its expectation is
$$\mathbb{E}(\sigma)=\sum_{k=2}^n \frac{n(n-1)}{k(k-1)}= n(n-1)\sum_{k=2}^n \frac1{k-1} - \frac1{k} = n(n-1)(1-\frac1{n}) = (n-1)^2 .$$
A: Just wish to add some sense to $f(k)$...
Let: 
$X_{i}$ - the number of balls of the color $i$ at time $t=0$. 
$A_{i}$ - the event that in the end all the balls are of the color $i$.
Using this notation:
$E(T|X_{1}=\lambda_{1},\ldots ,X_{n}=\lambda_{n}) =
\sum E(1_{A_{i}}T|X_{1}=\lambda_{1},\ldots,X_{n}=\lambda_{n})$.
But $E(1_{A_{i}}T|X_{1}=\lambda_{1},\ldots,X_{n}=\lambda_{n})$ depends only on $\lambda_{i}$ and is denoted by $f(\lambda_{i})$.
Using "first step" analysis we get:
$E(1_{A_{i}}T|X_{i}=k)=dE(1_{A_{i}}(T+1)|X_{i}=k+1)+
dE(1_{A_{i}}(T+1)|X_{i}=k-1)+(1-2d)E(1_{A_{i}}(T+1)|X_{i}=k)$
where $d=\frac{k(n-k)}{n(n-1)}$
One may compute (using Doob's theorem or otherwise) that $E(1_{A_{i}}|X_{i}=k)=\frac{k}{n}$.
And using that we obtain David Speyer's equation (**) for $f(k)$.
A: Consider just those sequences of selections that result in the final colour being $c$. If at some point during a sequence we have $k$ of the balls being this colour, we can define $E_k$ as the expected number of selections from here before all the balls are coloured $c$.
Doing this, we need to take account of the fact that not all selections are equally probable: each selection must be multiplied by the probability that it results in $c$ being the eventual colour. Happily, this probability is simply $k'/n$, where $k'$ is the number of balls coloured $c$ after this selection.
That gives us: $E_k = 1 + \frac{(k+1)(n-k)E_{k+1} + (k-1)(n-k)E_{k-1} + (n(n-1)-2k(n-k))E_k}{n(n-1)}$.
This simplifies to $2kE_k = \frac{n(n-1)}{n-k} + (k+1)E_{k+1} + (k-1)E_{k-1}$. We find from this that $E_1 = n/2 + E_2$, and generally if $E_{k-1} = w_{k-1}(n) + E_k$ then $E_k = w_k(n) + E_{k+1}$ with $w_k(n) = \frac{n(n-1)}{(n-k)(k+1)} + \frac{k-1}{k+1}w_{k-1}(n)$.
The required expectation, $E_1$, now resolves to:
$E_1 = \sum_{i=1}^{n-1}{w_i(n)}$
$ = n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{(n-i)(i+1)}(1 + \sum_{j=i+1}^{n-1}{ \prod_{k=i+1}^j{ \frac{k-1}{k+1} } }) }$
$ = n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{(n-i)(i+1)}(1 + \sum_{j=i+1}^{n-1}{ \frac{i(i+1)}{j(j+1)} }) }$
$ = n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{(n-i)(i+1)}(1 + i(i+1)(\frac{n-1}{n} - \frac{i}{i+1})) }$
$ = n(n-1) \sum_{i=1}^{n-1}{ \frac{1}{n} }$
$ = (n-1)^2$.
(Sorry, couldn't find how to get working multiline equations under jsMath, so I split them up.)
A: For n=3, one turn takes you 2 of one color and 1 of another.  To get to a single color you need to pick one of the 2 (prob=2/3), then pick the odd one (prob=1/2).  So the expected number of turns is 1+3=4
