35. [20] Barry picks infinitely many points inside a unit circle, each independently and uniformly at random, P , P , . . . . Compute the expected value of N , where N is the smallest integer such that 1 2 P is inside the convex hull formed by the points P , P , . . . , P . N +1 1 2 N Submit a positive real number E . If the correct answer is A , you will receive ⌊ 100 · max(0 . 2099 − | E − A | , 0) ⌋ points. Proposed by: Albert Wang, Rishabh Das Answer: 6 . 54 Solution: Clearly, N ≥ 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 · 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 · 2)(1 − 0 . 074 · 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)(1 + (1 − 0 . 074 · 2)(1 + (1 − 0 . 074 · 3)(1 + · · · ))) ≈ 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(-(2 ** 32),2 ** 32+1) y = randrange(-(2 ** 32),2 ** 32+1) if xx + yy < 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), 2 ** 32 , color='b', fill=False)

fix view to circle

plt.xlim(-2 ** 32 ,2 ** 32) plt.ylim(-2 ** 32 ,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[i], 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 [i], polygon [(i+1) % len( polygon )]

area_sum += area_of_triangle(point , polygon[i], 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 = [unit_circle_pt () for _ in range (3)] 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 - zstddev/np.sqrt(cur_trials), mean + zstddev/np.sqrt(cur_trials)) print (block+1, mean , stddev , ci)