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 
where 
and 
are relatively prime positive integers. Find 
.
Solution
Let 
denote the expected value for the number of loops if there are 
strings in the bag. We proceed to condition on what happens with the first string. There are 
other string ends, 1 of which is on the same string. If Eli ties the string to itself, then there are 
remaining strings (identical to starting with strings, and 1 loop). Otherwise, there are simply 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}.\]](http://latex.artofproblemsolving.com/8/e/d/8edbde858aeecc2569a74fabd64e86e9118c501f.png)
Obviously, 
(since the string will be tied to itself). Then, 
; continuing on, we have 
. Hence, 
. The desired answer is 
.
