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):
= pts[n:] + pts[:n]
rl = [d - pts[n] if d - pts[n] >= 0 else 2*pi + d - pts[n] for d in rl]
nl = [x - nl[i - 1] for i, x in enumerate(nl)][1:]
angles return sum(angles)
= 100000
runs = 10
N = defaultdict(int)
cnt_suc for n in range(3, N):
for _ in range(runs):
= [uniform(0, 2*pi) for _ in range(n)]
pts
pts.sort()= min([total_angle(pts, r) for r in range(n)])
min_angle if min_angle <= pi:
+= 1
cnt_suc[n] print("%d random points, Estimated probability %f, \
Theoretical probability %f" % (n, cnt_suc[n]/runs, n/2**(n-1)))