Puzzle time - Spaghetti loops
-
wrote on 18 Jul 2021, 10:54 last edited by
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?
-
wrote on 18 Jul 2021, 15:24 last edited by
By loop you mean loop of any length, right?
-
wrote on 18 Jul 2021, 16:42 last edited by
:::
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.
:::
-
wrote on 18 Jul 2021, 22:09 last edited by
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
:::
-
wrote on 19 Jul 2021, 10:04 last edited by
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.
-
wrote on 19 Jul 2021, 10:15 last edited by 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
-
wrote on 24 Jul 2021, 11:02 last edited by
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!