All tied up

Assume that we have reached into the bowl and pulled out one end. Then there are $2N - 1$ free ends left in the bowl. Therefore, there is a $1/(2N - 1)$ chance that a loop is formed by choosing the other end of the noodle that we are holding. And there is a $(2N - 2)/(2N - 1)$ chance that a loop is not formed. In the former case, we end up with one loop and $N - 1$ strands. In the latter case, we just end up with $N -1$ strands, because we have simply created a strand of twice the original length, and the length of a strand is irrelevant.

Therefore, after the first step, we see that no matter what happens, we end up with $N - 1$ strands and, on average, $1/(2N - 1)$ loops. We can now repeat this reasoning with $N - 1$ strands. After the second step, we are guaranteed to be left with $N - 2$ strands and, on average, another $1/(2N - 3)$ loops. This process continues until we are left with one strand, whereupon the final Nth step leaves us with zero strands, and we (definitely) gain one more loop.

So the average number of loops is $1/(2N-1)$ + $1/(2N-3)$ + ... + $1/3$ + $1$ . This first exceeds $3$ when $N = 57.$

We can set up a recurrence relation for the expected number of loops given n strands of noodles. Let E(n) be the expected number of loops for n strands. Now let us introduce one more strand (I imagine it is red) so that our bowl now has n+1 strands. The probability that the red strand ends up looped with just itself is $p=\frac{1}{2n+1}$ . This follows because one end of the red strand must end up joined to one of the other 2n+1 ends in the bowl. Each end is equally likely and just one of those ends is the other red end! If the red strand does not form a one strand loop with itself it must be incorporated into one of the loops formed by n strands. These observations lead to the recurrence relation

$E(n+1)=(1-p)E(n)+p(E(n)+1)=E(n)+p=E(n)+\frac{1}{2n+1}$

and obviously E(1) = 1

Now just crank the handle to get the series

$1+\frac{1}{3} + \frac{1}{5}+\frac{1}{7} + \frac{1}{9}+\frac{1}{11} + \frac{1}{13}+\dots (1)$

where summing the first n terms of the series gives the expected number of loops if we have n strands of noodles.

Summing 56 terms gives 2.994 and adding the $57^{th}$ gives 3.0033.

And so the minimum number required is $\boxed{57}$

Note added later.

I admit that I wrote a short program to evaluate (1), but subsequently I found another way to the answer.

As he often does, Euler (pronounced 'oiler') provided the lubricant.

We will use his result that, to a good approximation,

$\sum^{n}_{1}\frac{1}{k}=\ln{n}+\gamma$ where $\gamma=0.5772$ is the Euler-Mascheroni constant..

It is not too hard to see that the first n terms of (1) can be written as

$\sum^{2n-1}_{1}\frac{1}{k}-\frac{1}{2}\sum^{n-1}_{1}\frac{1}{k}$

Now use Euler's result to approximate this as

$\ln{(2n-1)}+\gamma-\frac{1}{2}\left(\ln{(n-1)}+\gamma \right)$

This simplifies to

$\ln{\left(\frac{2n-1}{\sqrt{n-1}}\right)+\frac{\gamma}{2}}\dots(2)$

Provided n is not too small, this formula approximates the expected number of loops with n strands of noodle.

We can also use this formula to find the number of terms (n) which are needed to make (1) exceed 3. First make a crude estimate by approximating the argument of the log function in (2)

$3\approx\ln{(2\sqrt{n})}+\frac{\gamma}{2}$

It is easy to make n the subject of this formula yielding $n\approx 56.6$

Then trying 56 and 57 in (2) yields partial sums 2.994 and 3.0033 agreeing spectacularly well with the results found by actually summing the series.

Bravo Euler!

This problem is another candidate for being handled by indicator random variables.

Every time a pair of ends is joined, the number of strands of noodles in the bowl goes down by one (either one strand is turned into a loop, or else two strands are joined into one). If we let $Z_j$ be the number of loops formed when the $j$ th pair of ends is joined, then $Z = Z_1 + Z_2 + Z_3 + \cdots + Z_N$ is the total number of loops formed, and hence $\mathbb{E}[Z] \; = \; \sum_{j=1}^N \mathbb{E}[Z_j] \; = \; \sum_{j=1}^N \mathbb{P}[Z_j = 1]$ Just before the $j$ pair of ends is joined, there are $N+1-j$ strands in the bowl. If we pick one end, then the probability that we form a loop is just the probability that we pick the other end of that loop, ouf of the $2(N+1-j)-1$ other ends that could be chosen. Thus $\mathbb{P}[Z_j=1] \; = \; \tfrac{1}{2N+1-2j}$ and hence $\mathbb{E}[Z] \; = \; \sum_{J=1}^N \tfrac{1}{2N+1-2j} \; = \; \sum_{j=1}^N \tfrac{1}{2j-1}$ which first exceeds $3$ when $N=\boxed{57}$ .