Semicircle Coverage

Problem

Semicircle Coverage

Solution 1

Each semicircle is bounded by two, diametrically opposite, points. The $n$ pairs of points divide the circle into $2n$ regions (which can be proved by induction.) A point on the circle may belong to a given semicircle, or to its complement. Hence, the probability that a given point on the circle is in one of the semicircles is $2^{-1}.$ The probability that it is covered by none of the $n$ semicircles is $2^{-n}.$ Further, a point belongs to exactly one of the $2n$ regions. If the point is not covered by the semicircles, so is the region it belongs to. Thus, the probability that at least one of those regions is not covered by the semicircles is $2^{-n}(2n)=2^{-n+1}n.$ The probability that the entire circle is covered is then $1-2^{-n+1}n.$

For $n=1,$ the formula gives the probability of $0,$ which is obviously true because a single semicircle only covers half a circle, not the whole of it. For $n=2,$ the probability is also $0,$ although two semicircles with the same end points cover the entire circle. The probability of this is clearly $0.$ For $n=3,$ the formula gives the probability $\displaystyle \frac{1}{4}.$

Solution 2

Consider $n$ semi-circles. Identify the semi-circles by the polar angle of their starting points. The start and end for the semi-circles are defined such that all the semi-circles get traversed in the same sense (clockwise or anti-clockwise) from the start to the end point. Set the polar angle origin at the start point of one of the semi-circles (label it as $S_0$) and sort the other start points in increasing order going from $0$ to $2\pi$ (label them as $S_i$, $i\in{1,2,...,n-1}$). Consider the $n$ intervals between successive starting points: ${l_1,l_2,...,l_n}$, such that $l_n=2\pi-S_{n-1}$ and $l_i=S_i-S_{i-1}$ for $1\lt i\lt n$. The sum of these intervals is $2\pi$. For the semi-circles to cover the circle completely, none of the intervals can be greater than $\pi$. The probability of this event is given by

$\displaystyle \begin{align} P(n)&=1-\sum_{i=1}^n P(l_i>\pi)~\text{(Only one interval can be greater than $\pi$ at a time)} \\ &=1-n\cdot P(l_1>\pi)~\text{(Symmetry}) \\ &=1-n\cdot\frac{\int_{l_1=\pi}^{2\pi}\int_{l_2=0}^{2\pi-l_1}\int_{l_2=0}^{2\pi-l_1-l_2}...\int_{l_{n-1}=0}^{2\pi-l_1-l_2...-l_{n-2}} dl_{n-1}dl_{n-2}...dl_2dl_1}{\int_{l_1=0}^{2\pi}\int_{l_2=0}^{2\pi-l_1}\int_{l_2=0}^{2\pi-l_1-l_2}...\int_{l_{n-1}=0}^{2\pi-l_1-l_2...-l_{n-2}} dl_{n-1}dl_{n-2}...dl_2dl_1} \\ &=1-n\frac{(2\pi-\pi)^{n-1}}{(2\pi)^{n-1}}=1-\frac{n}{2^{n-1}}. \end{align}$

Note, going from the inner-most to the outer-most integral, the first integral gives $(2\pi-l_1-l_2...-l_{n-2})$, the second one $(2\pi-l_1-l_2...-l_{n-3})^2/2!$, the third one $(2\pi-l_1-l_2...-l_{n-4})^3/3!$ and on. The only difference between the numerator and the denominator is in the final integral and only because of the different limits.

Acknowledgment

This is a simplified (2D) version of the problem of covering a sphere with hemispheres.

 

|Contact| |Front page| |Contents| |Probability|

Copyright © 1996-2018 Alexander Bogomolny

 63414766

Search by google: