Number of Wire Loops
Problem
Solution
Let the expected number of loops for $n$ wires be $f(n)$. There are $\displaystyle {2n\choose 2}=2n^2-n$ ways of choosing two ends from $n$ wires. Out of these, $n$ cases will result in a wire forming a self loop with $n-1$ wire segments remaining. The other $2n^2-2n$ cases will result in no self loop with just $n-1$ wire segments remaining. Thus,
$\displaystyle \begin{align} \left[2n^2-n\right]f(n)&=n\left[1+f(n-1)\right]+\left[2n^2-2n\right]f(n-1) \\ \Rightarrow~f(n)&=f(n-1)+\frac{1}{2n-1}. \end{align}$
$f(1)=1$. Thus,
$\displaystyle f(n)=\sum_{k=1}^{n}\frac{1}{2k-1} =\sum_{k=1}^{2n}\frac{1}{k}-\frac{1}{2}\sum_{k=1}^{n}\frac{1}{k} =H_{2n}-\frac{H_n}{2}.$
Thus,
$\displaystyle f(2018)=H_{4036}-\frac{H_{2018}}{2}\sim 4.787.$
Acknowledgment
This is problem 7 from the Wrangle contest at the Joint Mathematics Meetings 2018. The solution by Amit Itagi.
|Contact| |Front page| |Contents| |Probability|
Copyright © 1996-2018 Alexander Bogomolny71924503