Mock AIME I 2012 Problems/Problem 6

Problem

Eli has 5 strings. He begins by taking one end of one of the strings, and tying it to another end of a string (possibly the same string) chosen at random. He continues on by tying two randomly selected untied ends together until there are no more untied ends, and only loops remain. The expected value of the number of loops that he will have in the end can be expressed as $\frac{a}{b}$ where $a$ and $b$ are relatively prime positive integers. Find $a+b$.

Solution

Let $E_n$ denote the expected value for the number of loops if there are $n$ strings in the bag. We proceed to condition on what happens with the first string. There are $2n-1$ other string ends, 1 of which is on the same string. If Eli ties the string to itself, then there are $n-1$ remaining strings (identical to starting with $n-1$ strings, and 1 loop). Otherwise, there are simply $n-1$ remaining strings, and 0 loops. Since he chooses an end to tie at random, we have \[E_n = \frac{1}{2n-1} \cdot \left(1+E_{n-1}\right)+\frac{2n-2}{2n-1}\cdot E_{n-1} = \frac{1}{2n-1} + E_{n-1}.\] Obviously, $E_1 = 1$ (since the string will be tied to itself). Then, $E_2 = \frac{1}{2\cdot 2 - 1} + E_1 = \frac{1}{3} + 1$; continuing on, we have $E_n = \sum_{k=1}^n \frac{1}{2n-1}$. Hence, $E_5 = 1 + \frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{9}=\frac{563}{315}$. The desired answer is $a+b=563+315=\boxed{878}$.