Difference between revisions of "2005 Canadian MO Problems/Problem 3"

Latest revision as of 13:35, 9 June 2011

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.

@@ Line 7: / Line 7: @@
 ==Solution==
-{{solution}}
+(a) Let <math>H</math> be the convex hull of <math>S</math>, and choose any three vertices <math>V_1, V_2, V_3</math> of <math>H</math>.
+Now, draw a line <math>l_1</math> through <math>V_1</math> such that all points of <math>S</math> lie on one side of <math>l_1</math>. (This is possible because <math>H</math> is convex and contains <math>S</math>.) Define <math>l_2</math> and <math>l_3</math> similarly.
+For <math>i = 1, 2, 3</math>, let <math>m_i</math> be the line perpendicular to <math>l_i</math> passing through <math>V_i</math>, and let <math>m_i</math> hit the circle at point <math>P_i</math> on the side of <math>l_i</math> opposite <math>S</math>.
+Now, each <math>P_i</math> is closer to <math>V_i</math> than any other point in <math>S</math>.
+Since vertices <math>V_1, V_2, V_3 \in H</math> are also in <math>S</math>, we are done.
+(b) Describe the circle as the curve <math>r = 1</math> in polar coordinates. We will construct a set <math>S</math> with an arbitrary number of elements satisfying the desired property. Let <math>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</math>. It is easy to see that for any point <math>P</math> on the circle, <math>P</math> is at most <math>\frac{\sqrt{3}}{2}</math> away from one of the <math>V_i</math>. Therefore, if we also include points <math>Q_i</math> on any of the line segments <math>OV_i</math> (<math>O</math> is the center), where <math>OQ_i < 1 - \frac{\sqrt{3}}{2},</math> then no point can be chosen on the circle which is closer to one of the <math>Q_i</math> then the <math>P_i</math>.
+Thus <math>S</math> is as desired.
 ==See also==
 *[[2005 Canadian MO]]
+{{CanadaMO box|year=2005|num-b=2|num-a=4}}
 [[Category:Olympiad Combinatorics Problems]]

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

Page

Toolbox

Search

Difference between revisions of "2005 Canadian MO Problems/Problem 3"

Latest revision as of 13:35, 9 June 2011

Problem

Solution

See also