Library / /125 of 1394

, 2020

Geometry Difficulty 4.8 AIME Find the answer United States

Problem:
A collection $\mathcal{S}$ of $10000$ points is formed by picking each point uniformly at random inside a circle of radius $1$ . Let $N$ be the expected number of points of $\mathcal{S}$ which are vertices of the convex hull of the $\mathcal{S}$ . (The convex hull is the smallest convex polygon containing every point of $\mathcal{S}$ .) Estimate $N$ .

An estimate of $E>0$ will earn $\max (\lfloor 22-|E-N|\rfloor, 0)$ points.

Proposed by: Shengtong Zhang

Solution

Solution:
Here is $\mathrm{C}++$ code by Benjamin Qi to estimate the answer via simulation. It is known that the expected number of vertices of the convex hull of $n$ points chosen uniformly at random inside a circle is $O\left(n^{1 / 3}\right)$ . See "On the Expected Complexity of Random Convex Hulls" by Har-Peled.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.