Puzzle time - Spaghetti loops
-
-
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.
-
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!