Difference between revisions of "2020 IMO Problems/Problem 6"
Etmetalakret (talk | contribs) |
|||
(5 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
− | Problem | + | == Problem == |
− | + | Prove that there exists a positive constant <math>c</math> such that the following statement is true: | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | Consider an integer <math>n > 1</math>, and a set <math>S</math> of n points in the plane such that the distance between any two different points in <math>S</math> is at least <math>1</math>. It follows that there is a line <math>\ell</math> separating <math>S</math> such that the distance from any point of <math>S</math> to <math>\ell</math> is at least <math>cn^{- \frac{1}{3}}</math>. | |
+ | |||
+ | (A line <math>\ell</math> separates a set of points <math>S</math> if some segment joining two points in <math>S</math> crosses <math>\ell</math>.) | ||
+ | |||
+ | ''Note''. Weaker results with <math>cn^{- \frac{1}{3}}</math> replaced by <math>cn^{- \alpha}</math> may be awarded points depending on the value | ||
+ | of the constant <math>\alpha > \frac{1}{3}</math>. | ||
+ | |||
+ | == Solution == | ||
+ | |||
+ | For any unit vector <math>v</math>, let <math>a_v=\min_{p\in S} p \cdot v</math> and <math>b_v = \max_{p\in S} p\cdot v</math>. If <math>b_v - a_v\geq n^{2/3}</math> then we can find a line <math>\ell</math> perpendicular to <math>v</math> such that <math>\ell</math> separates <math>S</math>, and any point in <math>S</math> is at least <math>\Omega(n^{2/3}/n) = \Omega(n^{-1/3})</math> away from <math>\ell</math>. | ||
Suppose there is no such direction <math>v</math>, then <math>S</math> is contained in a box with side length <math>n^{2/3}</math> by considering the direction of <math>(1, 0)</math> and <math>(0, 1)</math>, respectively. Hence, <math>S</math> is contained in a disk with radius <math>n^{2/3}</math>. Now suppose that <math>D</math> is the disk with the minimum radius, say <math>r</math>, which contains <math>S</math>. Then, <math>r=O(n^{2/3})</math>. Since the distance between any two points in <math>S</math> is at least <math>1</math>, <math>r=\Omega(\sqrt{n})</math> too. | Suppose there is no such direction <math>v</math>, then <math>S</math> is contained in a box with side length <math>n^{2/3}</math> by considering the direction of <math>(1, 0)</math> and <math>(0, 1)</math>, respectively. Hence, <math>S</math> is contained in a disk with radius <math>n^{2/3}</math>. Now suppose that <math>D</math> is the disk with the minimum radius, say <math>r</math>, which contains <math>S</math>. Then, <math>r=O(n^{2/3})</math>. Since the distance between any two points in <math>S</math> is at least <math>1</math>, <math>r=\Omega(\sqrt{n})</math> too. | ||
− | Let <math>p</math> be any point in <math>S</math> on the boundary of <math>D</math>. Let <math>\ell_1</math> be the line tangent to <math>D</math> at <math>p</math>, and <math>\ell_2</math> the line obtained by translating <math>\ell_1</math> by distance <math>1</math> towards the inside of <math>D</math>. Let <math>H</math> be the region sandwiched by <math>\ell_1</math> and <math>\ell_2</math>. It is easy to show that both the area and the perimeter of <math>H\cap D</math> is bounded by <math>O(\sqrt{r})</math> (since <math>r=\Omega(\sqrt{n})</math>). Hence, there can only be <math>O(\sqrt{r})=O(n^{1/3})</math> points in <math>H\cap S</math>, by that any two points in <math>S</math> are distance <math>1</math> apart. Since the width of <math>H</math> is <math>1</math>, there must exist a line <math>\ell</math> parallel to <math>\ell_1</math> such that <math>\ell</math> separates <math>S</math>, and | + | Let <math>p</math> be any point in <math>S</math> on the boundary of <math>D</math>. Let <math>\ell_1</math> be the line tangent to <math>D</math> at <math>p</math>, and <math>\ell_2</math> the line obtained by translating <math>\ell_1</math> by distance <math>1</math> towards the inside of <math>D</math>. Let <math>H</math> be the region sandwiched by <math>\ell_1</math> and <math>\ell_2</math>. It is easy to show that both the area and the perimeter of <math>H\cap D</math> is bounded by <math>O(\sqrt{r})</math> (since <math>r=\Omega(\sqrt{n})</math>). Hence, there can only be <math>O(\sqrt{r})=O(n^{1/3})</math> points in <math>H\cap S</math>, by that any two points in <math>S</math> are distance <math>1</math> apart. Since the width of <math>H</math> is <math>1</math>, there must exist a line <math>\ell</math> parallel to <math>\ell_1</math> such that <math>\ell</math> separates <math>S</math>, and any point in <math>S</math> is at least <math>1/O(n^{1/3}) = \Omega(n^{-1/3})</math> away from <math>\ell</math>. Q.E.D. |
+ | |||
+ | Note. One can also show that <math>\Omega(n^{-1/3})</math> is best possible. | ||
+ | |||
+ | == Video solution == | ||
+ | https://www.youtube.com/watch?v=dTqwOoSfaAA [video covers all day 2 problems] | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | {{IMO box|year=2020|num-b=5|after=Last Question}} | ||
+ | |||
+ | [[Category:Olympiad Geometry Problems]] |
Latest revision as of 11:30, 14 May 2021
Contents
Problem
Prove that there exists a positive constant such that the following statement is true:
Consider an integer , and a set
of n points in the plane such that the distance between any two different points in
is at least
. It follows that there is a line
separating
such that the distance from any point of
to
is at least
.
(A line separates a set of points
if some segment joining two points in
crosses
.)
Note. Weaker results with replaced by
may be awarded points depending on the value
of the constant
.
Solution
For any unit vector , let
and
. If
then we can find a line
perpendicular to
such that
separates
, and any point in
is at least
away from
.
Suppose there is no such direction , then
is contained in a box with side length
by considering the direction of
and
, respectively. Hence,
is contained in a disk with radius
. Now suppose that
is the disk with the minimum radius, say
, which contains
. Then,
. Since the distance between any two points in
is at least
,
too.
Let be any point in
on the boundary of
. Let
be the line tangent to
at
, and
the line obtained by translating
by distance
towards the inside of
. Let
be the region sandwiched by
and
. It is easy to show that both the area and the perimeter of
is bounded by
(since
). Hence, there can only be
points in
, by that any two points in
are distance
apart. Since the width of
is
, there must exist a line
parallel to
such that
separates
, and any point in
is at least
away from
. Q.E.D.
Note. One can also show that is best possible.
Video solution
https://www.youtube.com/watch?v=dTqwOoSfaAA [video covers all day 2 problems]
See Also
2020 IMO (Problems) • Resources | ||
Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Last Question |
All IMO Problems and Solutions |