Number of Wire Loops

Problem

Number of Wire Loops

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 Bogomolny
[an error occurred while processing this directive]
[an error occurred while processing this directive]