You have a bag containing $n$ balls of $n$ different colours. Select 2 balls randomly (in order, so there's a first and a second), repaint the first in the same colour as the second, and replace both balls in the bag. Keep on doing this once per minute until all balls in the bag are the same colour.
What is the expected time this will take?

(Edit to make sure the balls are all of different colours at the start. In the original version, it was $n$ balls of $m$ different colours. Apologies to anyone who started working on the problem in that form.)

  • 1
    $\begingroup$ Is the initial color of each ball chosen at random? If not, it seems likely the answer will depend on the initial color distribution. Or did you mean $n$ balls of each of $m$ different colors? $\endgroup$ Jun 6, 2015 at 18:17
  • 1
    $\begingroup$ The way I heard this puzzle, when you draw two balls out of the bag, you only count it as a try if the colors are different. This version may still have a nice answer. $\endgroup$
    – Lopsy
    Jun 6, 2015 at 19:02
  • $\begingroup$ that's some fast-drying paint! $\endgroup$
    – JLee
    Jun 6, 2015 at 19:38
  • 5
    $\begingroup$ you got a lot of balls you know that $\endgroup$
    – d'alar'cop
    Jun 6, 2015 at 22:23
  • 3
    $\begingroup$ @Moti I did ask for "the expected time" in the OP! $\endgroup$ Jun 7, 2015 at 9:16

3 Answers 3


This question has been asked on Math Overflow. A beautiful answer was given by Ori Gurel-Gurevich, which I reproduce below.

Assume the balls and colors are both numbered $1,\dots,n$, with ball $i$ initially colored $i$.

Let $P(i,j)$ denote the action of painting ball $i$ the color of ball $j$. In this process, we perform a sequence of actions $P(i_1,j_1),P(i_2,j_2),\dots$, where $(i_k,j_k)$ is randomly chosen from the pairs where $i_k\neq j_k$, until all balls are the same color.

Here is a different process. Let $C(i,j)$ denote the action of taking every ball whose color is $i$ and painting it the color $j$. Perform the actions $C(i_1,j_1),C(i_2,j_2),\dots,$ with $i_k,j_k$ chosen randomly as before, until all balls are the same color. Call this the "new process".

The key to simplifying this problem is this brilliant observation: performing the actions $$ P(i_1,j_1),P(i_2,j_2),\dots, P(i_T,j_T) $$ to the initial setup has the same effect as performing the actions $$ C(i_T,j_T),C(i_{T-1},j_{T-1}),\dots, C(i_1,j_1) $$ to the initial setup. In words, reversing the order and replacing $P$ with $C$ does not change the resulting coloring.

It is somewhat difficult to explain why this is true (anyone who has an intuitive explanation should feel free to edit it in), but this example should convince you. Suppose have four balls, so the initial state is [1,2,3,4]. When we perform the actions $P(1,2), P(2,4), P(3,1), P(4,1)$, the resulting color distribution is [2,4,2,2], as shown below: $$ [1,2,3,4]\stackrel{P(1,2)}{\to}[2,2,3,4]\stackrel{P(2,4)}{\to}[2,4,3,4]\stackrel{P(3,1)}{\to}[2,4,2,4]\stackrel{P(4,1)}{\to}[2,4,2,2] $$ When the actions $C(4,1),C(3,1),C(2,4),C(1,2)$ are performed, the result is also [2,4,2,2], as claimed: $$ [1,2,3,4]\stackrel{C(4,1)}{\to}[1,2,3,1]\stackrel{C(3,1)}{\to}[1,2,1,1]\stackrel{C(2,4)}{\to}[1,4,1,1]\stackrel{C(1,2)}{\to}[2,4,2,2] $$

The symmetry implied by the bold statement means that the original process has the same average runtime as the new process, so we may analyze the expected runtime of the new process instead.

It turns out to be much easier to analyze the new process. If there are $k$ colors present at some point, then after performing a $C(i,j)$ action, the number of colors present will remain the same or decrease by $1$. It decreases by 1 with probability $\frac{k(k-1)}{n(n-1)}$, since this is the probability that both $i$ and $j$ are a color which was already present. Thus, the time it takes to decrease from $k$ colors to $k-1$ is a geometric random varaible, with expected time $\frac{n(n-1)}{k(k-1)}$, so the expected time it takes to go from $n$ colors to $1$ color is $$ \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)\left(1-\frac1n\right)=(n-1)^2 $$ The first step follows since $\frac1{k(k-1)}=\frac1{k-1}-\frac1{k}$. The second follows since the sum is telescoping.

Thus, the expected time is $(n-1)^2$.

  • $\begingroup$ The two processes are related as follows: The result of the first $k$ "$C$"-steps is the coloring that would result from the last $k$ "$P$"-steps if we performed them starting with each ball its own color. The "$C$" process amounts to looking at the draws in reverse order (the ball identities drawn, not the colors) and keeping track of the color-rearrangement that will be done by the steps we've seen. $\endgroup$
    – Karl
    Jul 19, 2022 at 20:50
  • $\begingroup$ So the "colors" present after $k$ steps of the backwards process are actually the identities of the "influential balls" whose colors are carried through the last $k$ steps of the original process. In that sense, this solution's core observation is about how prepending a step to a segment of the process affects the number of influential balls. $\endgroup$
    – Karl
    Jul 20, 2022 at 4:57
  • $\begingroup$ And I think that's the general form of this "time reversal" approach. When studying a process that involves a sequence of steps, it's natural to try to say something about what appending a step does, but we can also investigate the effect of prepending a step. $\endgroup$
    – Karl
    Jul 20, 2022 at 4:57


BEST SOLUTION (based on values of $n_\omega$): $(n-1)^2$ minutes.
$n-1$ minutes is an ideal solution
$\infty$ is an invalid trollish solution.

Answer One - Invalid Troll

I say that the answer is $\infty$, by allowing the choosing and painting of balls to be an infinite time, meaning that the process is never completed. thus, the answer is $\infty$ and we're done! $■$

(after reading comments) So you do mean time... How interesting. I failed to observe the "once per minute" bit. My general solutions is this: $\color{blue}{\Phi(n)}$ (see lower down)

Answer Two - $n_\omega$

This assumes that "expected time" is the same as "number of steps".

Experimental trial

$Step\>1$:$\text{Choose: }(\color{blue}{4},\color{green}{1})$ $\text{Resultant set: }\{\color{blue}{ball},\color{red}{ball},\color{purple}{ball},\color{blue}{ball}\}$
$Step\>2$:$\text{Choose: }(\color{blue}{1},\color{purple}{3})$ $\text{Resultant set: }\{\color{blue}{ball},\color{red}{ball},\color{blue}{ball},\color{blue}{ball}\}$
$Step\>3$:$\text{Choose: }(\color{red}{2},\color{blue}{1})$ $\text{Resultant set: }\{\color{red}{ball},\color{red}{ball},\color{blue}{ball},\color{blue}{ball}\}$
$Step\>4$:$\text{Choose: }(\color{red}{2},\color{blue}{3})$ $\text{Resultant set: }\{\color{red}{ball},\color{red}{ball},\color{red}{ball},\color{blue}{ball}\}$
$Step\>5$:$\text{Choose: }(\color{red}{3},\color{blue}{4})$ $\text{Resultant set: }\{\color{red}{ball},\color{red}{ball},\color{red}{ball},\color{red}{ball}\}$


Five steps for an experiment of $n=4$. It makes sense that, within a few iterations, a good deal of colours will disappear; a minimum of one colour will disappear within the first iteration. In this example, by step 2, we see that the original population of colours has been reduced from 4 to 2.

Computer- & Math-aided Portion

(to be accomplished with computers! The answer is easier to find if you know what you are looking for.)

You can't hate python. FEEL THE POWER OF PYTHON! This is how I obtain $n_\alpha$.

from random import *

class Ball:
    def __init__(self,colour):
        self.colour = colour

    def change_colour(self,ball):
        self.colour = ball.colour

def allColour(list):
    b = list[0].colour
        for i in range(len(list)):
            if not (b == list[i].colour):
                return False
            b = list[i].colour
    return True

def ball_sim(n):
    rq = list(range(n))
    for i in range(n):
        rq[i] = Ball(i)
    trials = 0
    if n == 1 or int(n) != n:
        return 1
    while not allColour(rq):
        samp = sample(list(range(len(rq))),2)
        trials += 1
    return trials

def s(n,m):
    avg = 0
    for qk in range(n):
        avg += ball_sim(m)
    return avg / n

while True:
    n = input("(integer) n = ")

Now, what this does, it takes an $n$ as an input, does 100,000 trials of a simulation of the steps, and takes the average step amount.


Definition 1: Each $n$ has:

  1. an upperbound (called $n_\mu$),
  2. a lowerbound (called $n_\lambda$),
  3. an average (given by python; called $n_\alpha$),
    1. a lowerbound with $t$ trials (designated $n_\alpha^t$; supposedly more accurate with higher values of $t$, and
  4. a real answer (called $n_\omega$).

Also let $s(n)$ be the seed of $n$, that is, the colour list original to $n$, and let $s_i(n)$ be the colour list on the $i$th step.

Definition 2: Let $c(b_i)$ designate the colour of ball $b_i$; any two balls selected for a given step are ordered in a coordinate pair, $(b_i,b_j)$. $b_i$ represents the ball at the $i$th position in $s(n)$. (I assume that a possible objective is to find $n_\lambda$ for an arbitrary $n$, perhaps using a function rule(s).)

Let's call this function $\Phi(n)$.

For $n=1$: $n$ is below the domain. I take it that that $1_\mu=1_\lambda=1$.

For $n=2$:

Theorem 1: $2_\mu=2_\lambda=1$ Proof. Suppose that $(b_0,b_1)$ is selected. Then, $b_0$ is coloured the same as $b_1$, $c(b_0)=c(b_1)$, and, since $\{b_0,b_1\}=s(2)$, we are done. Suppose the flipside is true, that $(b_1,b_0)$ is selected. Likewise, $b_1$ is coloured the same as $b_0$, $c(b_1)=c(b_0)$, and we are done. $■$

Theorem 2: For $n>2$, $n_\mu\le+\infty$.
Since there is the possibility (though however unlikely) that we will experience a cyclic behaviour in the choosing of balls (e.g. choosing $(b_i,b_j)$, then choosing $(b_j,b_i)$, then choosing $(b_i,b_j)$...). $■$

($n_\alpha$ based on a $100$-sized sample unless otherwise specified. This will become less and less accurate as $n$ increases; i.e., it is sufficiently accurate for ideally small values of $n$, where typically $\left|\left\lfloor n_\alpha\right\rceil-n_\alpha\right|\ll 0$)

For $n=3$: $3_\alpha=3.99$. To arrive at $3_\lambda$, we choose an ideal scenario: Each trial, one ball is converted. So, in the first trial, there are $2$ different colours, then, in the last trial, there is only one colour. So, there are two trials. Also note, it seems that $n_\omega=4$; it is expected that every $n_\omega\approx n_\alpha$.

Theorem 3: $n_\lambda=n-1$.
This states that the absolute minimum for any $n$-bag is $n-1$. Consider that, before there are any balls painted, $n$ colours. Then, ideally, on turn $1$, there are $n-1$ balls. On turn $2$, there are $n-2$ balls, etc. So, on the $k$th turn, there are ideally $n-k$ colours left among the balls. Thus, on the $n-1$th turn, there are ideally $n-(n-1)=n-n+1=1$ colours left, and, since no lower number is possible for a remainder of colours, $n-1$ must be the last ideal turn.$■$

Definition 2: $I(n)=n-1$. (The Ideal function)

Note: The first claim is essentially proven in an ideal scenario; for a bag of $n$ balls of $n$ different colours, ideally, the time expected in an idealist scenario is $n-1$ minutes. Obviously, for $n\in\mathbb Z \land n>1$, as the other cases are trivial/impossible.

From now on, the results are computer-aided more. For $n=4$, $n_\alpha=9.00172^{10^5}$. We can infer that $n_\omega=9$.

n      = 4
trials = 1
n      = 4
trials = 10
n      = 4
trials = 100
n      = 4
trials = 1000
n      = 4
trials = 10000
n      = 4
trials = 100000

For $n=5$, $n_\alpha^{10^5}=16.00694$, and seems to imply $n_\omega=16$.

n      = 5
trials = 1
n      = 5
trials = 10
n      = 5
trials = 100
n      = 5
trials = 1000
n      = 5
trials = 10000
n      = 5
trials = 100000

(the code you see here is as follows:

while True:
    n=int(input("n      = "))
    t=int(input("trials = "))

; that is, the code used to find certain values of $n_\lambda^t$.)

I thereby conclude that $\Phi(n)=(n-1)^2$.

Tabulated Results

(also see here) $$\begin{array}{c|c|c|c|c}n&n_\omega&t&n_\alpha^t&(n-1)^2\\\hline 1&0&\varnothing&0&0\\ 2&1&\varnothing&1&1\\ 3&4&10^2&3.99&4\\ 4&9&10^5&9.00172&9\\ 5&16&10^5&16.00694&16 \end{array}$$

A Formal Proof

The former is a proof leaning on computers and their results. I want to find a mathematical proof of this fact.

We know the answer is $(n-1)^2$ (or at least, as it seems), so all that needs to be done is to prove it.

But first, what does the result being $(n-1)^2$ signify? (Note that this is my thought process; this does not yet reveal an actual answer.)

Doing some preliminary research, I found an interesting identity which holds for $k\le n$: $$(x+y)^n=\sum_{k=0}^n\binom nk x^{n-k}y^k$$ I thought this might yield some information, yet it revealed nothing new.


  • $\begingroup$ I'm not familiar with python, but it looks like your allColor() function effectively only checks if the last two colors are the same. Your numbers are definitely too small. For n=3, the correct answer is 4. $\endgroup$ Jun 8, 2015 at 15:21
  • $\begingroup$ Oh. I see what you mean. Lemme toggle that. Thanks! $\endgroup$ Jun 8, 2015 at 21:20
  • $\begingroup$ $(n-1)^2$ is correct, but eek! That's a long and nasty-looking proof (which I don't have time to read just now). Also I know nothing about Python ... does that mean I won't be able to understand this answer even when I do have time? $\endgroup$ Jun 8, 2015 at 22:42
  • $\begingroup$ @randal'thor Oh... well, the proof is based on limits of values arrived at by python; are you familiar with JavaScript? If so, I can reproduce it in that. Worst comes to worst, I'll just comment the carp out of the code. $\endgroup$ Jun 8, 2015 at 22:44
  • $\begingroup$ @CᴏɴᴏʀO'Bʀɪᴇɴ I'm not really familiar with any programming language - sorry. Not typical for an SE user, I know! :-) $\endgroup$ Jun 8, 2015 at 22:45

The answer is


Let's say $a(i)$ is the total of "rounds" in which the $i_{th}$ colour is present, before the colour $i$ disappears or becomes the only one.
This is equivalent to the Gambler's ruin problem, where the expected time of $a(i)$ is $n-1$.
We also believe in the linearity of expectation, and we already know that the colours are $n$ and the expectation of $a(n)$ is $n-1$.
Thus, we can deduce that the expected time $t(n)$ to make all the balls of the same colour is:


Why did we divide by $2$? Simply because each "round" involves two different colours!

Big credits to @Russ Woodroofe for his solution here

  • $\begingroup$ Nope, I'm afraid you've slightly misunderstood the problem. The MathOverflow post you link is a slightly different problem, in which you always select two differently coloured balls. Here you select two balls each time and 'repaint' vacuously if they're the same colour, so the expected time is longer than n(n-1)/2 minutes. $\endgroup$ Jun 7, 2015 at 15:46
  • $\begingroup$ Ah I didn't notice the randomness! I won't delete this answer for now because it may help others finding a solution, if there's one. $\endgroup$
    – leoll2
    Jun 7, 2015 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.