Source

I got this problem from Rustan Leino, who got it from Dave Detlefs, who got it from the following impressive collection of math problems.

I solved it and wrote up my solution.

Problem

Given $N$ points randomly distributed around the circumference of a circle, what's the probability that all $N$ points lie on the same semi-circle?

Solution
Reveal

The probability is $\frac{N}{2^{N-1}}$, by the following reasoning.

Because the points are chosen from a continuous domain, the probability that any two given points are exactly coincident is zero. Similarly, the probability that any two given points are exactly opposite each other on the circle is zero. Since there are a finite number of points, the probability that either of these things happens to any pair of points is also zero. Thus, from here on, we assume that no two points are exactly coincident or opposite.

Number the points $1$ through $N.$ For any point $i$, let the event $E_i$ be "All points lie on the semi-circle that starts at point $i$ and goes clockwise." Let the event $E$ be "All points lie on the same semi-circle."

First, observe that if any $E_i$ occurs, then $E$ occurs. After all, since the points all lie on the semi-circle starting at point $i$, there's a semi-circle on which all the points lie. We conclude that $\bigcup_i E_i \Rightarrow E.$

Second, observe that if $E$ occurs, then some $E_i$ occurs. Here's why. If $E$ occurs, then there's a semi-circle $S$ on which all points lie. Consider the first point $i$ that you come to as you travel clockwise on $S.$ All points lie on $S$, so they also lie on the semi-circle that starts at point $i$ and goes clockwise. In other words, $E_i$ occurs. We conclude that $E \Rightarrow \bigcup_i E_i.$

Since $E \Rightarrow \bigcup_i E_i$ and $\bigcup_i E_i \Rightarrow E$, we have $E = \bigcup_i E_i.$

Now, observe that events $E_i$ and $E_j$ can't co-occur if $i \neq j.$ Recall our assumption that points $i$ and $j$ can't be exactly coincident or opposite on the circle. So, if $E_i$ and $E_j$ both occur, then one can go less than halfway around the circle clockwise from point $i$ to get to point $j$, then less than halfway around the circle clockwise from point $j$ to get to point $i.$ But, then, one can travel all the way around the circle with only two moves each less than halfway. This is impossible, so we conclude that the events $\{E_i\}$ are mutually exclusive.

Since the events $\{E_i\}$ are mutually exclusive, the probability of at least one happening is the sum of their probabilities. In other words, $P(\bigcup_i E_i) = \sum_i P(E_i).$ Thus, since $E = \bigcup_i E_i,$ we have $P(E) = \sum_i P(E_i).$

Now, let's calculate $P(E_i).$ This is the probability that all points other than $i$ appear no more than halfway clockwise of $i.$ For each point other than $i$, the probability that it appears no more than halfway clockwise of $i$ is $1/2.$ The points are chosen independently, so the probability that this happens to all $N-1$ such points is $\frac{1}{2^{N-1}}.$

Thus, \[ P(E) = \sum_i P(E_i) = \sum_{i=1}^N \frac{1}{2^{N-1}} = \frac{N}{2^{N-1}}. \] By definition of $E$, this is the probability we're asked to calculate.