Puzzle : Noodles

PS : This post contains a flawed solution followed by a correct solution. Solution posted earlier was flawed as pointed out by vikas in a comment following this post. Fixed solution is written in green.

I stumbled upon this page and saw interesting collection of puzzle. Most of them I had already solved. Found this one particularly interesting.

Problem : There is this weird man who goes to a noodle shop and orders noodle soup. He asks for exactly 100 noodles in his soup.

Once his noodle-soup arrives, he gets to work. He extracts two noodle ends from under the soup, ties a knot, and lets it slip into the soup again. He does the above 100 times – so that now all the noodle ends are tied.

Now he reaches his hand into the soup. What is the probability that he would extract a garland containing all the 100 noodles?

Flawed Solution : Interesting thing to note is that everytime the man chooses those noodle ends which are not tied already. This way in 100 steps the man can tie all the noodle ends. If there is no loose noodle ends then it must be the case that noodles might form a circle. If he can extract a garland containing all the 100 noodles means that he had actually constructed a circle containing 100 noodles.

Initially, me and Deepanjan both went on a slightly wrong direction by actually trying to calculate the probabilities of failure after first step, second step and so on.

After a few minutes I realized that this problem is nothing but to find the number of partitions of a given integer, 100, in this case. So the answer is 1/p(n) = 1/190,569,292

Those of you, who are not able to see the connection between two problems , let me give you an example. Say there are only four noodles. What are the possible configurations of noodles at the end of 4 steps? Following number indicates the size of the circles in each configuration.

4

3 1

2 1 1

2 2

1 1 1 1

This is nothing but to find the number of ways to split a given integer. Once I realized this reduction, wikipedia was handy enough to provide me with the exact figures.

Fixed Solution : The reason why the solution mentioned above was flawed is that it assumed that each end configuration is equally likely, which is not the case.

The correct solution goes like this. At each step we want to calculate the probability that the noodle ends being tied should belong to different noodles. Also, I am giving a generalized solution for any n.

If we are given n noodles. Initially, we have 2n noodle ends. Number of ways to choose one end from these is ${2n \choose 1}$. Now, the other end should come from a different noodle. Number of ways to choose the second end is ${2n-2 \choose 1}$. We need to divide this figure by 2 because of symmetry, because for a noodle ends named A and B, B-A or A-B should not be considered as different possibility.

So for the first step we have

$\frac{{2n \choose 1} {2n-2 \choose 1}}{2 {2n \choose 2}} = \frac{2n-2}{2n-1}$

For the second step we will have, n-1 different noodles and 2n-2 different noodle ends. We can repeat the same procedure again.

Probability that we can form a garland of all n noodle can be given by

$\displaystyle \prod _{i=2} ^{i=n} \frac {2i-2}{2i-1}$

For n=100, Probability of success is : $1 \cdot \frac{2}{3} \cdot \frac{4}{5} \dots \frac{198}{199}$

–Saurabh Joshi

Tags: , ,

4 Responses to “Puzzle : Noodles”

1. vikas Says:

hmm is this correct? What if there are only two noodles. According to you the probability of forming a single ring would be 1/2. But lets name the two noodles A and B and the corresponding ends A1,A2 and B1, B2. If in the first step he ties A1 to A2 or B1 to B2 he wont have a single garland. And these are the only 2 possible cases where he wont have a garland. In other 4 cases
A1-B1, A1-B2, A2-B1, A2-B2 he will end up with a garland. So the probability of having a garland is 4/6/

2. Linked list and probability « Me, Myself and Mathematics Says:

[…] Me, Myself and Mathematics Saurabh Joshi’s Blog about math, algorithms, theorems, puzzles …. « Puzzle : Noodles […]

3. Pratik Poddar Says:

Can someone find a mistake in my solution?

The problem is same as to calculate the following

If n vertices are identical
No. of ways to form one garland = 1
No. of ways to find more that one garland = x