2005 Canadian MO Problems/Problem 3

(Redirected from 2005 Canadian MO/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$.

Thus $S$ is as desired.

See also

2005 Canadian MO (Problems)
Preceded by
Problem 2
1 2 3 4 5 Followed by
Problem 4