Noodles

Solution

Let \(E_n\) be the expected number of closed loops formed from \(n\) noodles. The clean way to see this is to track the process by the number of open chains remaining. At the beginning, each noodle is an open chain, so there are \[ n \] open chains. Each time you tie together two loose ends, exactly one of two things happens: \[ \text{either two different chains are joined into one longer chain,} \] or \[ \text{the two ends of the same chain are tied together, creating a closed loop.} \] In either case, the number of open chains decreases by \(1\). So when there are \(k\) open chains left, there are exactly \[ 2k \] free ends. Now imagine the next tie is made. Pick one free end. Among the remaining \[ 2k-1 \] ends, exactly one of them is the other end of the same chain. If that matching is chosen, that chain closes into a loop. So when there are \(k\) chains left, the probability that the next tie creates a new loop is \[ \frac{1}{2k-1}. \] Define an indicator variable \(I_k\) by \[ I_k = \begin{cases} 1, & \text{if a loop is created when there are } k \text{ chains left},\\ 0, & \text{otherwise.} \end{cases} \] Then \[ \mathbb{E}[I_k] = \frac{1}{2k-1}. \] The total number of loops formed is \[ L = I_n + I_{n-1} + \cdots + I_1. \] Therefore, by linearity of expectation, \[ \mathbb{E}[L] = \sum_{k=1}^{n} \mathbb{E}[I_k] = \sum_{k=1}^{n} \frac{1}{2k-1}. \] So the expected number of closed loops is \[ \boxed{\sum_{k=1}^{n} \frac{1}{2k-1}}. \] This can also be written as \[ \boxed{1+\frac13+\frac15+\cdots+\frac{1}{2n-1}}. \] Using harmonic numbers, an equivalent form is \[ \boxed{H_{2n}-\frac12 H_n}. \] For example: \[ n=1 \quad \Rightarrow \quad 1 \] \[ n=2 \quad \Rightarrow \quad 1+\frac13=\frac43 \] \[ n=3 \quad \Rightarrow \quad 1+\frac13+\frac15=\frac{23}{15}. \] So the expected number of loops grows roughly like \[ \frac12 \ln n \] for large \(n\), but the exact answer is \[ \boxed{\sum_{k=1}^{n} \frac{1}{2k-1}}. \]