Difference between revisions of "2005 Canadian MO Problems/Problem 3"
(→Solution) |
|||
(4 intermediate revisions by 3 users not shown) | |||
Line 6: | Line 6: | ||
==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== | ==See also== | ||
*[[2005 Canadian MO]] | *[[2005 Canadian MO]] | ||
+ | |||
+ | {{CanadaMO box|year=2005|num-b=2|num-a=4}} | ||
+ | |||
+ | [[Category:Olympiad Combinatorics Problems]] |
Latest revision as of 12:35, 9 June 2011
Problem
Let be a set of
points in the interior of a circle.
- Show that there are three distinct points
and three distinct points
on the circle such that
is (strictly) closer to
than any other point in
,
is closer to
than any other point in
and
is closer to
than any other point in
.
- Show that for no value of
can four such points in
(and corresponding points on the circle) be guaranteed.
Solution
(a) Let be the convex hull of
, and choose any three vertices
of
.
Now, draw a line through
such that all points of
lie on one side of
. (This is possible because
is convex and contains
.) Define
and
similarly.
For , let
be the line perpendicular to
passing through
, and let
hit the circle at point
on the side of
opposite
.
Now, each
is closer to
than any other point in
.
Since vertices
are also in
, we are done.
(b) Describe the circle as the curve in polar coordinates. We will construct a set
with an arbitrary number of elements satisfying the desired property. Let
. It is easy to see that for any point
on the circle,
is at most
away from one of the
. Therefore, if we also include points
on any of the line segments
(
is the center), where
then no point can be chosen on the circle which is closer to one of the
then the
.
Thus is as desired.
See also
2005 Canadian MO (Problems) | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 | Followed by Problem 4 |