Noodles Part 1

A dish contains 100 strands of cooked spaghetti. See the picture below:Capture

Two ends of spaghetti are chosen at random and tied together. For example:

Capture2

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?

Capture36

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.

Capture 5

For the first noodle, I started with the left end. I could tie it to itself:Capture6

Then I would have to tie the other noodle to itself and I would not have a big loop:

Capture7

Another option would be to tie the left end to the end below it:

Capture8

Then I would tie the remaining 2 ends together to make a loop!

Capture9

My last option would be to tie the top left end to the right bottom end:

Capture10

Then I would have to tie the remaining 2 ends together:

Capture11

Do some untwisting, and make a loop!

Capture115

To recap, with 2 noodles, we have a 2/3 probability of getting a one big loop. How about 3 noodles?

Capture12

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:

Capture13

By doing this, we create one long noodle, which we can move around to form:

Capture14

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.

Capture15

We multiply this by the 2-noodle case to get

\frac{2}{3} \times \frac{4}{5}

You can continue this logic and find the probability for 5 noodles is:

\frac{2}{3} \times \frac{4}{5} \times \frac{6}{7} \times \frac{8}{9}

Now I noticed a pattern. Combine the top and bottom numbers:

\frac{2 \times 4 \times 6 \times 8}{3 \times 5 \times 7 \times 9}

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.

Capture4

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:

f(n) = \cfrac{2 \cdot 4 \cdot 6 \cdot 8 \dots (2n-2)}{ 3 \cdot 5 \cdot 7 \cdot 9 \dots (2n-1)}

Using double factorial notation, we can rewrite it as:

f(n) = \cfrac{(2n-2)!!}{(2n-1)!!}

Using basic double factorial identities2, we can convert the double factorials into regular factorials:

f(n) = \cfrac{2^n n!}{2n} \times \cfrac{2^n n!}{(2n)!}

And use some algebra to simplify:

f(n) = \cfrac{2^{2n} n! n!}{2n (2n)!}

Enter, the Stirling Approximation!3

n! \approx \sqrt{2n\pi} \left( \cfrac{n^n}{e^n} \right)

f(n) \approx \cfrac{2^{2n}}{2n} \times \cfrac{\sqrt{2n\pi} \left( \frac{n^n}{e^n} \right) \times \sqrt{2n\pi} \left( \frac{n^n}{e^n} \right)}{\sqrt{4n\pi} \left( \cfrac{(2n)^{2n}}{e^{2n}} \right)}

We can cancel a bunch of terms to get:

f(n) \approx \cfrac{\sqrt{\pi n}}{2n} = \sqrt{\cfrac{\pi }{4n}}

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 😛

1The Mathematics Teacher, Volume 109, Number 3, October 2015, page 201.

2https://en.wikipedia.org/wiki/Double_factorial

3https://en.wikipedia.org/wiki/Stirling’s_approximation

 

Advertisements

Leave a comment

Filed under Uncategorized

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s