This is a problem via fakalin.

You have 10 pieces of string, each with two ends. You randomly pick two ends of string (possibly from the same string, possibly from different ones) and tie them together, creating either a longer piece of string or a loop. You keep doing this until you run out of free ends.

What is the expected number of loops you end up with?

Things to note are the following:

- Once a loop is made from a string, it is removed from further consideration.
- Picking two ends from the same string immediately makes a loop.
- Picking two ends from different strings makes a longer string.

So in the end, no matter which two ends are picked, we have one fewer open string than we started with.

Let \(f(n)\) be the expected number of loops with \(n\) open strings. We know \(f(1)=1\). With \(n\) strings, the probability of picking two ends from the same string is \(n/\binom{2n}{2}\). So:

\(f(n) = n/\binom{2n}{2} (f(n-1) + 1) + (1 – n/\binom{2n}{2}) f(n-1)\)
\(= f(n-1) + n/\binom{2n}{2} = f(n-1) + n / [2n (2n - 1) / 2] = f(n-1) + 1 / (2n-1)\)

That is, \(f(n) = \sum_{i=1}^n 1/(2i-1)\), \(f(10) = 1841/863\).

For large \(n\), this sum does not converge, in fact it is obvious that \(f(n)\) grows like \(\log n\).