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:

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\).

The sets under consideration are sets of Happy Meals. Happy Meals are the same or different only based on the sequence of toys received.

We have subsets now with different properties. Let \(A\subset \{1,\ldots,8\}\) be a set of toys, and \(T_{A}\) be the set of Happy Meals that do not contain toys in \(A\). For example, \(T_{\{1\}}\) is the set of Happy Meals missing toy 1. What we really want to find is the size of this set:

which contain just those Happy Meals that aren’t missing any toys.

Here’s where we apply the inclusion-exclusion principle. The size of the second part above is:
\(\sum_{i=1}^{8} (-1)^{i-1} (\sum_{A:|A|=i} |T_A|)\)
or
\((|T_{\{1\}}|+ \cdots +|T_{\{8\}}|) – (|T_{\{1\}}\cap T_{\{2\}}|+ \cdots +|T_{\{7\}}\cap T_{\{8\}}|) + (|T_{\{1\}}\cap T_{\{2\}}\cap T_{\{3\}}| + \cdots ) – \cdots\)

Now, notice the following interesting fact:

because the Happy Meals that are missing toys in \(A\cup B\) are exactly those that do not contain toys in \(A\) and do not contain toys in \(B\). Further note that \(|T_A|=|T_B|\) if \(|A|=|B|\), because the number of Happy Meals only depends on the number of excluded toys that characterizes them. So replace \(|T_A|\) by \(N_{|A|}\)

Taking the above into consideration, we find the size of \(T_{\{1\}}\cup\cdots\cup T_{\{8\}}\) to be

Clearly, the number of Happy Meals that do not contain some particular pre-determined \(i\) toys is \(N_i = (8-i)^{16}\), so the size of the set is \(\sum_{i=1}^{8} (-1)^{i-1} {8 \choose i} (8-i)^{16}\) or \({8 \choose 1}7^{16} – {8 \choose 2}6^{16} + {8 \choose 3}5^{16} – {8 \choose 4}4^{16} + {8 \choose 5}3^{16} – {8 \choose 6}2^{16} + {8 \choose 7}1^{16} = 195119050093696\).

The answer to the original problem is

\((8^{16} – 195119050093696)/8^{16} = 343/1118 \approx 0.3068\).

The solution is at once generalizable to any number of toys and any number of Happy Meals.