2020 IMO Problems/Problem 6

Revision as of 11:29, 14 May 2021 by Etmetalakret (talk | contribs)

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.

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
Problem Last Question
All IMO Problems and Solutions
Invalid username
Login to AoPS