Points on a circle

Riddler Classic

If N points are generated at random places on the perimeter of a circle, what is the probability that you can pick a diameter such that all of those points are on only one side of the newly halved circle?

Solution

Each of the $N$ points determines a diameter of the circle. The probability of all the other $N-1$ points falling on one side of diameter determined by the first point is given by $\frac{1}{2^{N-1}}$. Therefore the probability of picking a diameter such that all of those points are on one side of the newly halved circle is $\sum_{i=1}^N\frac{1}{2^{N-1}} = \frac{N}{2^{N-1}}$.

Computational verification

from math import pi
from random import uniform
from collections import defaultdict

def total_angle(pts, n):
    rl = pts[n:] + pts[:n]
    nl = [d - pts[n] if d - pts[n] >= 0 else 2*pi + d - pts[n] for d in rl]
    angles = [x - nl[i - 1] for i, x in enumerate(nl)][1:]
    return sum(angles)

runs = 100000
N = 10
cnt_suc = defaultdict(int)
for n in range(3, N):
    for _ in range(runs):
        pts = [uniform(0, 2*pi) for _ in range(n)]
        pts.sort()
        min_angle = min([total_angle(pts, r) for r in range(n)])
        if min_angle <= pi:
            cnt_suc[n] += 1
    print("%d random points, Estimated probability %f, \
        Theoretical probability %f" % (n, cnt_suc[n]/runs, n/2**(n-1)))