IMO 2020 · 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 \(\ell\) separating \(S\) such that the distance from any point of \(S\) to \(\ell\) is at least \(cn^{-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^{-1/3}\) replaced by \(cn^{-\alpha}\) may be awarded points depending on the value of the constant \(\alpha>1/3\).

Official text of the problem. Official problem paper (PDF)

Solution

We prove that \(c=\frac1{20}\) works.

Let \(D\) be the largest distance between two points of \(S\), and choose \(A,B\in S\) with \(AB=D\). Choose coordinates so that \[ A=(0,0),\qquad B=(D,0). \] We have \(D\ge1\). Every point \(P=(x,y)\in S\) has distance at most \(D\) from both \(A\) and \(B\), so \[ 0\le x\le D,\qquad x^2+y^2\le D^2. \]

Observe that if \(0\le u<v\le D\) and no point of \(S\) has its \(x\)-coordinate strictly between \(u\) and \(v\), then the line \[ x=\frac{u+v}{2} \] crosses \(AB\) and has distance at least \((v-u)/2\) from every point of \(S\). Thus it suffices to find a sufficiently long gap between \(x\)-coordinates.

Case 1: \(D\ge n^{2/3}\).

List the \(x\)-coordinates of all points, including repetitions, as \[ 0=x_1\le x_2\le\cdots\le x_n=D. \] The \(n-1\) consecutive gaps sum to \(D\), so one has length at least \(D/(n-1)\). Its midpoint gives a separating line whose distance from every point is at least \[ \frac{D}{2(n-1)} \ge \frac{n^{2/3}}{2n} =\frac12n^{-1/3} \ge\frac1{20}n^{-1/3}. \]

Case 2: \(D<n^{2/3}\).

Consider the points in the cap \[ T=\{(x,y)\in S:D-1\le x\le D\}, \] and write \(m=|T|\). Since \(B\in T\), we have \(m\ge1\). For every point in \(T\), \[ y^2\le D^2-x^2\le D^2-(D-1)^2=2D-1. \] Put \(h=\sqrt{2D-1}\). Thus \(T\) lies in a rectangle of width \(1\) and height \(2h\).

Partition \(T\) into the points with \(x\le D-\frac12\) and those with \(x>D-\frac12\). Within either part, two points have horizontal separation at most \(\frac12\). Their distance is at least \(1\), so their vertical separation is at least \[ \sqrt{1-\left(\frac12\right)^2}=\frac{\sqrt3}{2}. \] Consequently, if either part contains \(k\ge1\) points, ordering their vertical coordinates gives \[ (k-1)\frac{\sqrt3}{2}\le2h, \qquad\text{hence}\qquad k\le1+\frac{4h}{\sqrt3}. \] This upper bound also holds for an empty part. Therefore \[ m\le2+\frac{8h}{\sqrt3} =2+\frac8{\sqrt3}\sqrt{2D-1} \le10\sqrt D, \] where the last inequality uses \(D\ge1\) and \(2D-1\le3D\).

Now list the \(x\)-coordinates of the points in \(T\), including repetitions: \[ t_1\le t_2\le\cdots\le t_m=D, \] and set \(t_0=D-1\). Since \[ \sum_{i=1}^{m}(t_i-t_{i-1})=1, \] some gap has length at least \(1/m\). Its interior contains no \(x\)-coordinate of a point of \(S\): points outside \(T\) have \(x<D-1\).

By our initial observation, the midpoint of this gap gives a separating line whose distance from every point of \(S\) is at least \[ \frac1{2m}\ge\frac1{20\sqrt D} \ge\frac1{20}n^{-1/3}. \]

Both cases establish the result. \(\square\)

The solution was checked against the official IMO shortlist solutions.