22
$\begingroup$

A man orders spicy noodle and leek soup from a restaurant, but gets bored while eating.
When he gets bored, there are exactly 100 noodles in the soup. Because he is bored, he decides to play a game with his soup.

He will take two noodle ends from under the soup (being careful not to burn himself), tie them into a knot, and put them back into the soup again. He is very good at tying knots.

Once he has done this 100 times, all the noodle ends are tied.

He reaches into the soup and pulls out a loop made of tied noodles. What is the probability that it contains all 100 noodles?

|improve this question
$\endgroup$
  • 2
    $\begingroup$ Do chains count? Like say noodle A is completely wrapped around noodle B, and noodle B is also wrapped around noodle C, does picking up A include picking up C? $\endgroup$ – DqwertyC Oct 18 '17 at 14:35
  • 1
    $\begingroup$ @Dqwerty I don't think so but I think it would make a more unusual (which is good) puzzle. As is, this question is an enjoyable math problem but still something I could see on a test. $\endgroup$ – kaine Oct 18 '17 at 15:23
  • 3
    $\begingroup$ I think I totally misunderstood the question XP. What you're looking for is one giant loop of all the noodles, right? I was thinking a small loop with a ton of other small loops stuck on it, like keys on a keychain. That problem would not be something I could see in a test. $\endgroup$ – DqwertyC Oct 18 '17 at 16:00
  • 1
    $\begingroup$ @DqwertyC Your version of the puzzle allowing chains is intriguing but it would require lots of additional information about the physical dimensions involved. It would be completely unsolvable on the basis of the information given here (and, I suspect, pretty much unsolvable, period). $\endgroup$ – user2390246 Oct 18 '17 at 16:42
  • $\begingroup$ How does he find his noodle ends? If he finds a noodle centre and works his way to the end, then the odds of drawing a noodle chain from the soup increase proportional to that chain's length? $\endgroup$ – Scott Oct 19 '17 at 4:04
16
$\begingroup$

My guess is

$\frac{2^{198}(99!)^2}{199!} \approx 0.0887335$

Reasoning

Let $p_n$ be the probability of a soup containing $n$ noodles resulting in one giant loop after a corresponding procedure (i.e, tying ends together $n$ times). It is clear that on the very first tying, the man will either tie the ends of a single noodle or tie together the ends of two different noodles. In the latter case, he will effectively have created one new noodle by joining two original noodles together and thereby reduce the problem to that of the case for $n-1$ noodles. In the former, there is no way to result in a single loop containing all of the noodles. The probability of joining the ends of a single noodle on the first tying of knots is $\frac{n}{\binom{2n}{2}} = \frac{1}{2n-1}$, otherwise we arrive at the corresponding problem for $n-1$.

That is,

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

Hence

$p_{100} = \frac{198}{199} p_{99} = \ldots = \prod_{k=1}^{99} \frac{2k}{2k+1} = \frac{2^{198}(99!)^2}{199!}$

|improve this answer
$\endgroup$
  • $\begingroup$ For those of us without the patience to enter that into Wolfram|Alpha or Mathematica, that's about this many. (Not putting the answer itself in here to avoid spoiling it for those who want to try) $\endgroup$ – Nic Hartley Oct 18 '17 at 16:42
  • 2
    $\begingroup$ feel free to add the percentage of success to your answer. $\endgroup$ – sousben Oct 18 '17 at 19:47
  • $\begingroup$ I'm actually quite surprised that the chance is so high. Though I guess this is simply a variation on the "unique birthday" problem, where layman estimates are way off-base. $\endgroup$ – Flater Oct 19 '17 at 13:12
14
$\begingroup$

If he ever creates a loop before tying the last knot, then he fails because he has created a loop that is too small which will never be tied to the rest. I am assuming that being linked like the links in a chain does not count, but only being combined into one single long loop.
At any stage when he pulls out one end, there is therefore exactly one other end that he must avoid tying it to.
So for the first end, there are 199 other ends he can use as the second end, and only 1 fails. The probability of success is 198/199 for this first knot.
The situation is now that there are 99 noodles left, with 198 ends. For the next knot, the probability of success is similarly 196/197. For the one after that 194/195, and so on.
He has to successfully avoid loops every time except the last, so the combined probability of this is:

$$\frac{198}{199}\frac{196}{197}\frac{194}{195}...\frac{2}{3} = \frac{198^2*196^2*...2^2}{199*198*197*...*3*2} = \frac{2^{198}*99!^2}{199!} = 0.0887335$$

So there is about 9% probability of success.

|improve this answer
$\endgroup$
5
$\begingroup$

Lets say he had x noodles at the start, and call P(x) the chance of creating one big loop. At x = 1 P(x) = 1. At x = 2 $$P(X) = \frac{2}{3}$$, because there is only 1 "other end" which is wrong for the first tie of the three(he already holds one, just looking for an other to tie with). What is important to see is at x noodles P(X) = P(first tie is not a 1 noodle loop) * P(x-1), because x-1 noodle is the same than x noodle with 1 good tie(not connecting the same noodle's two end). At x noodles P(first tie is not a 1 noodle loop) = $$\frac{2*x-2}{2*x-1}$$. So $$P(100) = \frac{198}{199} * P(99) = \frac{198}{199} * \frac{196}{197} * P(98) = ... = \frac{198}{199} * \frac{196}{197} * ... * \frac{4}{5} * \frac{2}{3}= \frac{(2^{99}*99!)^2}{199!}$$

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.