This content is from http://www.alethis.net/mpotd/mpotd.php?id=00131
You have a plate of spaghetti in front of you (no sauce!). You pick two ends and tie them together. Then you pick two more ends and tie them together. Continue until there are no free ends left.
If there were n spaghettis originally, what is the probability that you now have a single giant loop consisting of all the spaghettis?
Pick the first end at random, from the 2n ends. When you pick the second end, you have 2n-1 choices, and exactly one of them (the other end of the spaghetti you chose) will create a loop at this step. The probability of creating a loop at this step is therefore 1/(2n-1), so the probability of not creating a loop is (2n-2)/(2n-1).
If we don’t create a loop at the first step, then at the second step, we have the same situation, but with 2n-2 free ends. Pick one end at random, and the probability of forming a loop at this step is 1/(2n-3), since there’s only one other end that is attached to the end you chose. The probability of not creating a loop at the second step is therefore (2n-4)/(2n-3).
When we eventually get down to two remaining segments, the same logic applies: pick one end, and of the remaing three ends, one forms a loop, while the other two allow us to proceed to the last step, where a single giant loop is formed. The probability is 2/3 of not creating a loop at this second last step.
To end up with a single loop at the end, we must not create a loop at any of the intermeditate steps, so the probability of this is:
| 2n – 2 | 2n – 4 | 2n – 6 | … | 2 |
| 2n – 1 | 2n – 3 | 2n – 5 | 3 |
| = | 2n – 2 | 2n – 2 | 2n – 4 | 2n – 4 | 2n – 6 | 2n – 6 | … | 2 | 2 |
| 2n – 1 | 2n – 2 | 2n – 3 | 2n – 4 | 2n – 5 | 2n – 6 | 3 | 2 |
| = | 4n-1(n – 1)!2 |
| (2n – 1)! |
The first few probabilities are:
| n | prob. |
|---|---|
| 1 | 1 |
| 2 | 2/3 |
| 3 | 8/15 |
| 4 | 16/35 |
Nic 