Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2005 Canadian MO Problems/Problem 3"
(→‎Solution)
 
(2 intermediate revisions by 2 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]]
 
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 12: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.

See also

2005 Canadian MO (Problems)
Preceded by
Problem 2 		1 • 2 • 3 • 4 • 5 Followed by
Problem 4
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_Canadian_MO_Problems/Problem_3&oldid=39396"