Puzzle time - Spaghetti loops

[jon-nyc]

The 100 ends of 50 strands of cooked spaghetti are paired at random and tied together. How many pasta loops should you expect to result from this process, on average?

[Klaus]

By loop you mean loop of any length, right?

[Klaus]

:::

I believe it's something like 1 + 1/2 + 1/3 + ... + 1/50.

The key insight is that the problem is equivalent to the number of cycles in a permutation of the numbers 1 to 50. The expected number of cycles of length n is 1/n.

:::

[jon-nyc]

Seems more like:

:::

1/99 + 1/98 + … 1/2 + 1/1.

Every time you randomly pick two ends from k strands, you have a 1/(2k-1) chance of creating a loop. Create one or not, you reduce the number of strands by 1.

Though solution doesn’t come until Saturday

:::

[Klaus]

Oh, I see. I made the implicit assumption that you'd only pair "left" ends with "right" ends, but you want me to pair anything with anything. I believe my solution is correct for the "pairing left with right" scenario. I'm not quite sure your solution is right for your scenario, though. Consider two strands of spaghetti. There are three equally likely outcomes, two with one loop and one with two loops, giving an average of 4/3. But your formula would yield 1+1/2+1/3.

[jon-nyc]

The formula 1/(2k-1) is right, and would give the 4/3 answer.

I wrote out the expansion wrong. It’s 1/99 + 1/97 + 1/95 …. + 1/5 + 1/3 + 1/1

[jon-nyc]

Official solution:

SOLUTION: The key here is to recognize that you start with 100 spaghetti-ends and each tying operation reduces the number of spaghetti-ends by two. The operation results in a new loop only if the first end you pick up is matched to the other end of the same strand. At step k, there are 100 - 2(k-1) ends, thus 100 - 2(k-1) - 1 = 101 - 2k other ends you could tie any given end to. In other words, there are 101 - 2k choices of which only one makes a loop; the others just make two strands into one longer one.

It follows that the probability of forming a loop at step k is 1/(101 - 2k). If X(k) is the number of loops (1 or 0) formed at step k, then the expected (that is, average) value of X(k) is 1/(101 - 2k). Since the final number of loops is X(1) + . . . + X(50), we conclude that on the average, the final loop count is

1/99 + 1/97 + 1/95 + . . . + 1/3 + 1/1

which is about 2.93777485; less than three loops!