Brainteasers & Puzzles

Colour Balls

Repainting a random ball to a second random ball's colour merges colour classes one drawing at a time. From n singleton colours the expected time to a monochrome box is (n-1)^2, and the final two-colour merge alone accounts for half of it.

solvedhard1 min

A box contains nn balls of nn different colours. At each step you draw an ordered pair of balls at random, repaint the first to match the colour of the second, and return both. How many steps on average until all the balls share a single colour?

Reveal solutionHide solution

#Repainting is a voter model

Drawing an ordered pair and repainting the first ball to match the second is the voter model on the complete graph. The box turns a single colour exactly once every ball descends from one common origin.

#Trace the colours backward

A ball's colour is a copy of whichever ball it last matched. Following those copy links backward in time, the nn starting colours form lineages that only ever merge and never split. Represent each surviving lineage by one token, so the token count equals the number of colours still present, falling from nn down to 11.

#Each merge is geometric

A backward step merges two tokens exactly when its ordered pair lands on two distinct surviving lineages, which with kk tokens left happens with probability k(k−1)n(n−1)\tfrac{k(k-1)}{n(n-1)}. So the wait to drop from kk tokens to k−1k-1 is geometric with mean n(n−1)k(k−1)\tfrac{n(n-1)}{k(k-1)}.

#Telescope

E[steps]=∑k=2nn(n−1)k(k−1)=n(n−1)∑k=2n(1k−1−1k)=n(n−1)(1−1n)=(n−1)2.(1)\E[\text{steps}] = \sum_{k=2}^{n} \frac{n(n-1)}{k(k-1)} = n(n-1)\sum_{k=2}^{n}\left(\frac{1}{k-1} - \frac{1}{k}\right) = n(n-1)\left(1 - \frac{1}{n}\right) = (n-1)^2. \tag{1}
5 to 44 to 33 to 22 to 1colors merging
Backward in time the colors are tokens that only merge. Dropping from k colors to k-1 takes an expected n(n-1)/(k(k-1)) steps, and the stages telescope to (n-1) squared. The last merge of the final two colors alone is half the wait.

#The last merge dominates

The answer is (n−1)2(n-1)^2. The final merge of the last two colours alone costs n(n−1)2\tfrac{n(n-1)}{2}, fully half the wait, since two thoroughly mixed colours are slow to tip over into one.