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)))