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 "2020 IMO Problems/Problem 6"
(→‎Solution)
 
(9 intermediate revisions by 3 users not shown)
Line 1: Line 1:
−
Problem 6. Prove that there exists a positive constant c such that the following statement is true:
+
== Problem ==
−
Consider an integer n > 1, and a set S of n points in the plane such that the distance between
+
Prove that there exists a positive constant <math>c</math> such that the following statement is true:
−
any two different points in S is at least 1. It follows that there is a line ℓ separating S such that the
 
−
distance from any point of S to ℓ is at least cn^(−1/3)
 
−
.
 
−
(A line ℓ separates a set of points S if some segment joining two points in S crosses ℓ.)
 
−
Note. Weaker results with cn^(−1/3)
 
−
replaced by cn^−α may be awarded points depending on the value
 
−
of the constant α > 1/3.
 
  
−
Proof. 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>0.5 n^{-1/3}</math> away from <math>\ell</math>.
+
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>.
  
−
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 taking <math>v</math> as <math>(1, 0)</math> and <math>(0, 1)</math>, respectively. Hence, <math>S</math> is contained in a disk with radius at most <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>.
+
(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>.)
  
−
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>. 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 no point in <math>S</math> is within distance <math>O(n^{-1/3})</math> to <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>.
  
−
EOF.
+
== 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.
 +
 
 +
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.
 +
~Shen Kislay kai
 +
 
 +
== 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 12:15, 3 September 2024

Problem

Prove that there exists a positive constant $c$ such that the following statement is true:

Consider an integer $n > 1$, and a set $S$ of n points in the plane such that the distance between any two different points in $S$ is at least $1$. It follows that there is a line $\ell$ separating $S$ such that the distance from any point of $S$ to $\ell$ is at least $cn^{- \frac{1}{3}}$.

(A line $\ell$ separates a set of points $S$ if some segment joining two points in $S$ crosses $\ell$.)

Note. Weaker results with $cn^{- \frac{1}{3}}$ replaced by $cn^{- \alpha}$ may be awarded points depending on the value of the constant $\alpha > \frac{1}{3}$.

Solution

For any unit vector $v$, let $a_v=\min_{p\in S} p \cdot v$ and $b_v = \max_{p\in S} p\cdot v$. If $b_v - a_v\geq n^{2/3}$ then we can find a line $\ell$ perpendicular to $v$ such that $\ell$ separates $S$, and any point in $S$ is at least $\Omega(n^{2/3}/n) = \Omega(n^{-1/3})$ away from $\ell$.

Suppose there is no such direction $v$, then $S$ is contained in a box with side length $n^{2/3}$ by considering the direction of $(1, 0)$ and $(0, 1)$, respectively. Hence, $S$ is contained in a disk with radius $n^{2/3}$. Now suppose that $D$ is the disk with the minimum radius, say $r$, which contains $S$. Then, $r=O(n^{2/3})$. Since the distance between any two points in $S$ is at least $1$, $r=\Omega(\sqrt{n})$ too.

Let $p$ be any point in $S$ on the boundary of $D$. Let $\ell_1$ be the line tangent to $D$ at $p$, and $\ell_2$ the line obtained by translating $\ell_1$ by distance $1$ towards the inside of $D$. Let $H$ be the region sandwiched by $\ell_1$ and $\ell_2$. It is easy to show that both the area and the perimeter of $H\cap D$ is bounded by $O(\sqrt{r})$ (since $r=\Omega(\sqrt{n})$). Hence, there can only be $O(\sqrt{r})=O(n^{1/3})$ points in $H\cap S$, by that any two points in $S$ are distance $1$ apart. Since the width of $H$ is $1$, there must exist a line $\ell$ parallel to $\ell_1$ such that $\ell$ separates $S$, and any point in $S$ is at least $1/O(n^{1/3}) = \Omega(n^{-1/3})$ away from $\ell$. Q.E.D.

Note. One can also show that $\Omega(n^{-1/3})$ is best possible. ~Shen Kislay kai

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_IMO_Problems/Problem_6&oldid=226305"