Q. A jar has N strings in it. You randomly pick up two loose ends and tie them up. You continue doing this until there are no more free ends. What is the expected number of loops in the jar?

A. This is another one of those puzzles which gets vastly simplified when you place it in a recursive perspective. A diagram with 3 strings would best explain the scenario. Ref figure below.

If there are 'n' strings, there are 2n loose ends to pick up from. The first loose end can be picked up randomly. While picking the second loose end, there are two possibilities.

It is part of the same string you just picked up ORIt is the loose end of another string. For 1), the probability of this event happening is

while for 2) it is 1 minus the above, giving

This implies that with probability 1/(2n-1), the expected number of strings will be 1 + P(n-1) and with probability (2n-2)/(2n-1) it will be P(n-1). This leads to the recursive formulation of the expected number of loops to be

If you re-arrange …

A. This is another one of those puzzles which gets vastly simplified when you place it in a recursive perspective. A diagram with 3 strings would best explain the scenario. Ref figure below.

If there are 'n' strings, there are 2n loose ends to pick up from. The first loose end can be picked up randomly. While picking the second loose end, there are two possibilities.

It is part of the same string you just picked up ORIt is the loose end of another string. For 1), the probability of this event happening is

while for 2) it is 1 minus the above, giving

This implies that with probability 1/(2n-1), the expected number of strings will be 1 + P(n-1) and with probability (2n-2)/(2n-1) it will be P(n-1). This leads to the recursive formulation of the expected number of loops to be

If you re-arrange …