, 2024

Solution:

Clearly, $N \geq 3$, and let's scale the circle to have area $1$. We can see that the probability to not reach $N=4$ is equal to the probability that the fourth point is inside the convex hull of the past three points. That is, the probability is just one minus the expected area of those $N$ points. The area of this turns out to be really small, and is around $0.074$, and so $(1-0.074)$ of all sequences of points make it to $N=4$. The probability to reach to the fifth point from there should be around $(1-0.074)(1-0.074 \cdot 2)$, as any four points in convex configuration can be covered with $2$ triangles. Similarly, the chance of reaching $N=6$ should be around $(1-0.074)(1-0.074 \cdot 2)(1-0.074 \cdot 3)$, and so on. Noting that our terms eventually decay to zero around term $1 / 0.074 = 13$, our answer should be an underestimate. In particular, we get
$$3 + (1-0.074)\left[1 + (1-0.074 \cdot 2)\left[1 + (1-0.074 \cdot 3)(1+\cdots)\right]\right] \approx 6.3$$
Guessing anything slightly above this lower bound should give a positive score.

Here is a Python code that simulates the result.

```
from random import randrange, getrandbits
import itertools, math
from tqdm import tqdm
import numpy as np
DEBUG = False
def unit_circle_pt():
while True:
x = randrange(-(232), 232+1)
y = randrange(-(232), 232+1)
if x*x + y*y < 2**64:
return (x, y)
def area_of_triangle(p1, p2, p3):
return abs((p2[0] - p1[0])*(p3[1] - p2[1]) - (p2[1] - p1[1])*(p3[0] - p2[0]))
def pt_inside_polygon(point, polygon):
# point is a pair
# polygon is an angle-sorted list of points that are the vertices of a convex polygon in some order
# area of polygon
# plot the polygon and the point
if DEBUG:
import matplotlib.pyplot as plt
# plot the big circle
circle = plt.Circle((0,0), 232, color='b', fill=False)
# fix view to circle
plt.xlim(-232,232)
plt.ylim(-232,2**32)
plt.gca().add_artist(circle)
# make the window to scale
plt.gca().set_aspect('equal', adjustable='box')
plt.plot([x for x,_ in polygon], [y for _,y in polygon])
plt.scatter([point[0]], [point[1]])
plt.show()
area = 0
for i in range(1, len(polygon)-1):
# add on area between points 0, i, i+1
area += area_of_triangle(polygon[0], polygon*, polygon[i+1])
# point is inside polygon if the area of the triangles formed by the point and each edge of the polygon sum to the area of the polygon
area_sum = 0
for i in range(len(polygon)):
# add on area between points point, polygon*, polygon[(i+1)%len(polygon)]
area_sum += area_of_triangle(point, polygon*, polygon[(i+1)%len(polygon)])
return area_sum == area
def convex_hull(points):
# sort by x, then y
points = sorted(points, key=lambda x: (x[0], x[1]))
# graham scan
# find the lowest point
lowest = points[0]
for p in points:
if p[1] < lowest[1]:
lowest = p
# sort by angle
points = sorted(points, key=lambda x: (math.atan2(x[1]-lowest[1], x[0]-lowest[0]), -x[1], x[0]))
# remove duplicates
points = list(k for k,_ in itertools.groupby(points))
# stack to hold the points
stack = []
for p in points:
while len(stack) > 1 and (stack[-1][0]-stack[-2][0])*(p[1]-stack[-2][1]) - (stack[-1][1]-stack[-2][1])*(p[0]-stack[-2][0]) <= 0:
stack.pop()
stack.append(p)
return stack
def pulse(horizon=1000):
cur =
for N in range(3, horizon):
pt = unit_circle_pt()
if pt_inside_polygon(pt, cur):
return N
cur = convex_hull(cur + [pt])
trials = 1000
blocks = 100000
cur_trials = 0
cur_sum = 0
results = []
for block in range(trials):
for _ in tqdm(range(blocks)):
results.append(pulse())
cur_trials += blocks
mean = np.mean(results)
stddev = np.std(results)
z = 5.0
ci = (mean - z*stddev/np.sqrt(cur_trials), mean + z*stddev/np.sqrt(cur_trials))
print(block+1, mean, stddev, ci)
```