Steps to Make Three Colored Balls Match

Worked Solution

How to Think About It: Only the *number of distinct colors* matters for stopping, so collapse the state to that count: start at $3$, absorb at $1$. The heuristic is state-lumping into a tiny Markov chain. The trap -- and it is the whole problem -- is assuming that grabbing two differently-coloured balls always merges the colours. It does not. Once you are at $2$ colours the pile is split $2{+}1$, and drawing the majority ball together with the lone one finishes the game only if the *lone* ball is the one repainted; repaint the majority ball instead and you land back in a $2{+}1$ split with the roles swapped. Missing that second failure route is what turns a correct $4$ into a too-clever $5/2$. For $n$ balls the colour count no longer collapses to a small chain, so part (b) instead follows one colour, whose count is a martingale, and conditions on that colour winning.

Quick Estimate: From $3$ distinct colours any pair you pull is two different colours, so step $1$ *always* drops you to $2$ colours -- exactly $1$ step, no randomness. From the $2$-colour state (split $2{+}1$, say $A,A,B$) there are $\binom{3}{2}=3$ equally likely pairs. The matched pair $\{A,A\}$ (probability $\tfrac13$) wastes the step outright. Each mixed pair (total probability $\tfrac23$) finishes only on the coin flip that repaints $B$ -- half the time. So the per-step success probability is $\tfrac23 \times \tfrac12 = \tfrac13$, a geometric taking $3$ steps. Total $\approx 1 + 3 = 4$. The estimate *is* the exact answer here: $\boxed{4}$.

Approach: Lump the state to the number of distinct colours, then write a first-step equation for the $2{+}1$ state, being careful to count *both* ways a step can fail to make progress.

Formal Solution: Let the state be the number of distinct colours, $E_s$ the expected steps to finish from state $s$.

State $3$ (configuration $1{+}1{+}1$): the two chosen balls are always different colours, so repainting either one yields a $2{+}1$ split -- you move to state $2$ with certainty. Hence $E_3 = 1 + E_2$.

State $2$ (configuration $2{+}1$: two balls of colour $A$, one ball of colour $B$): pick $2$ of $3$ balls, $\binom{3}{2}=3$ equally likely pairs, then flip a fair coin for which of the two is repainted.

• Both $A$ balls (probability $\tfrac13$): they already match, so repainting either changes nothing -- stay in state $2$.
• One $A$ and the $B$ (probability $\tfrac23$), then the coin:
• repaint $B$ to $A$ (probability $\tfrac12$): all three balls are $A$ -- reach state $1$, done;
• repaint that $A$ to $B$ (probability $\tfrac12$): the configuration becomes $A,B,B$ -- still a $2{+}1$ split, still state $2$.

So the step succeeds with probability $\tfrac23 \cdot \tfrac12 = \tfrac13$ and otherwise returns to state $2$: $$E_2 = 1 + \tfrac23 E_2 \;\Longrightarrow\; \tfrac13 E_2 = 1 \;\Longrightarrow\; \boxed{E_2 = 3}.$$ Then $E_3 = 1 + E_2 = 1 + 3 = 4$.

Part (b): $n$ balls. With $n$ colours the configuration is a partition of $n$, so the count of distinct colours no longer gives a tiny chain. Track a single colour instead. Note that a uniform pair plus a fair coin is the same as a uniform *ordered* pair (repainted ball, model ball) from the $n(n-1)$ ordered pairs.

*Step 1 -- One colour's count is a martingale.* Fix red and let $i$ be the number of red balls. The count rises by one when a non-red ball is repainted red and falls by one when a red ball is repainted another colour. Both have probability $$p_i = \frac{i(n-i)}{n(n-1)},$$ so the red count is a martingale, absorbed at $0$ or $n$.

*Step 2 -- Condition on the winner.* By optional stopping, red takes over from $i$ red balls with probability $i/n$; from the start ($i = 1$) every colour wins with probability $1/n$. By symmetry $E[T \mid c \text{ wins}]$ is the same for every colour $c$, so $E[T] = E[T \mid \text{red wins}]$.

*Step 3 -- The conditioned chain.* Conditioning on red winning reweights each move $i \to j$ by $h(j)/h(i)$ with $h(i) = i/n$ (a Doob $h$-transform). Given red wins, the count moves up with probability $p_i\,\frac{i+1}{i}$, down with probability $p_i\,\frac{i-1}{i}$, and stays with probability $1 - 2p_i$. It can never step from $1$ to $0$.

*Step 4 -- Solve the recursion.* Let $E_i$ be the expected remaining steps given $i$ red balls and that red wins, with $E_n = 0$. First-step analysis gives $$2p_i E_i = 1 + \frac{p_i}{i}\big[(i+1)E_{i+1} + (i-1)E_{i-1}\big].$$ Multiply by $i/p_i = \frac{n(n-1)}{n-i}$ and set $G_i = iE_i$, so $G_0 = G_n = 0$: $$G_{i+1} - 2G_i + G_{i-1} = -\frac{n(n-1)}{n-i}, \qquad 1 \le i \le n-1.$$ With $d_i = G_i - G_{i-1}$ this reads $d_{i+1} = d_i - \frac{n(n-1)}{n-i}$, so $d_i = d_1 - n(n-1)\sum_{k=1}^{i-1}\frac{1}{n-k}$. Since $\sum_{i=1}^{n} d_i = G_n - G_0 = 0$, $$n\,d_1 = n(n-1)\sum_{k=1}^{n-1}\frac{n-k}{n-k} = n(n-1)^2,$$ because each $k$ appears for the $n-k$ values $i = k+1, \ldots, n$. Hence $E[T] = E_1 = G_1 = d_1 = (n-1)^2$.

*Step 5 -- Check and evaluate.* $n = 2$ gives $1$ (one step always finishes) and $n = 3$ gives $4$, matching part (a). For $n = 5$ the expected number of steps is $(5-1)^2 = 16$. Solving the exact chain over all colour partitions for $n = 2, \ldots, 6$ gives $1, 4, 9, 16, 25$, and a simulation for $n = 5$ gives $16.01$.

Answer: (a) The expected number of steps is $E_3 = 4$. (b) For $n$ balls it is $(n-1)^2$, which is $16$ for $n = 5$.

*Verification.* Solving the exact Markov chain on the full colouring of the three balls (not the lumped count) gives $E = 4$ symbolically, and a $400{,}000$-run simulation of the stated rule gives $3.993$. Note that the merge-always model -- which would give $E_2 = 3/2$ and $E_3 = 5/2$ -- is not realisable by any symmetric repainting rule: from $A,A,B$ the pair $\{A,B\}$ must become either $A,A,A$ or $A,B,B$, and the second outcome keeps two colours alive.