2005 Canadian MO Problems/Problem 3

Problem

Let $S$ be a set of $n\ge 3$ points in the interior of a circle.

Show that there are three distinct points $a,b,c\in S$ and three distinct points $A,B,C$ on the circle such that $a$ is (strictly) closer to $A$ than any other point in $S$ , $b$ is closer to $B$ than any other point in $S$ and $c$ is closer to $C$ than any other point in $S$ .
Show that for no value of $n$ can four such points in $S$ (and corresponding points on the circle) be guaranteed.

Solution

(a) Let $H$ be the convex hull of $S$ , and choose any three vertices $V_1, V_2, V_3$ of $H$ .

Now, draw a line $l_1$ through $V_1$ such that all points of $S$ lie on one side of $l_1$ . (This is possible because $H$ is convex and contains $S$ .) Define $l_2$ and $l_3$ similarly.

For $i = 1, 2, 3$ , let $m_i$ be the line perpendicular to $l_i$ passing through $V_i$ , and let $m_i$ hit the circle at point $P_i$ on the side of $l_i$ opposite $S$ . Now, each $P_i$ is closer to $V_i$ than any other point in $S$ . Since vertices $V_1, V_2, V_3 \in H$ are also in $S$ , we are done.

(b) Describe the circle as the curve $r = 1$ in polar coordinates. We will construct a set $S$ with an arbitrary number of elements satisfying the desired property. Let $V_1 = \left(\frac{1}{2}, 0\right), V_2 = \left(\frac{1}{2}, \frac{\pi}{3}\right), V_3 = \left(\frac{1}{2}, \frac{2\pi}{3}\right) \in S$ . It is easy to see that for any point $P$ on the circle, $P$ is at most $\frac{\sqrt{3}}{2}$ away from one of the $V_i$ . Therefore, if we also include points $Q_i$ on any of the line segments $OV_i$ ( $O$ is the center), where $OQ_i < 1 - \frac{\sqrt{3}}{2},$ then no point can be chosen on the circle which is closer to one of the $Q_i$ then the $P_i$ .