Two ends of spaghetti are chosen at random and tied together. For example:
If this process continues until there are no more loose ends, what is the probability that all strands will form one big loop? In other words, what are the chances that this big mess is actually just a circle?
Seriously, take a guess. When I first read a version of this problem,1 I thought the answer must surely be less than 1%. Watch this:
Now you may think that I took a particularly well behaved group of noodles for the above animation. However, mathematically speaking, the probability of getting a single big loop is 9%, much higher that you probably guessed.
I want to walk you through some of the interesting twists and turns that it took for me to get the answer. First, I had to find a formula for calculating the above probability. My first method was to try less noodles. With 2 noodles, it seemed like I could figure out all the possibilities.
Then I would have to tie the other noodle to itself and I would not have a big loop:
Another option would be to tie the left end to the end below it:
Then I would tie the remaining 2 ends together to make a loop!
My last option would be to tie the top left end to the right bottom end:
Then I would have to tie the remaining 2 ends together:
Do some untwisting, and make a loop!
To recap, with 2 noodles, we have a 2/3 probability of getting a one big loop. How about 3 noodles?
Instead of going through all the probabilities, we can use a trick. If I tie the top left end of the noodle to the right end of the same noodle, I create an isolated loop like before. That is not good. So instead, consider tying the top left end to any other noodle end:
By doing this, we create one long noodle, which we can move around to form:
Voila! We are back to the 2-noodle case. Since there are 4 places I could tie the top left end (green), and 1 place I cannot (red, since it would make an isolated loop) I have a 4/5 chance.
We multiply this by the 2-noodle case to get
You can continue this logic and find the probability for 5 noodles is:
Now I noticed a pattern. Combine the top and bottom numbers:
We are actually just multiplying even numbers and dividing them by odd numbers! I was so excited! I went into excel, punched in the formula, and was thoroughly disappointed.
Apparently, multiplying 100 numbers got excessively big for my computer to handle. I needed a new approach. The noodle probability formula can be written as follows:
Using double factorial notation, we can rewrite it as:
Using basic double factorial identities2, we can convert the double factorials into regular factorials:
And use some algebra to simplify:
Enter, the Stirling Approximation!3
We can cancel a bunch of terms to get:
Finally, a formula my computer can handle! This formula will work for any number of noodles. Maybe you were wondering what number of noodles you would need for the probability to be below 1%. The formula states that we would need 7854 noodles! Personally, if you would have told me that before analyzing the problem, I would have thought you were out to lunch :P
1The Mathematics Teacher, Volume 109, Number 3, October 2015, page 201.