2020 IMO Problems/Problem 6

Problem 6. 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 ℓ 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 $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 $0.5 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 no point in $S$ is within distance $O(n^{-1/3})$ to $\ell$ . Q.E.D.

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

Page

Toolbox

Search

2020 IMO Problems/Problem 6