IMO 2020 Problem 6

Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 1m17s

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}$.


2020 IMO (Problems) • Resources
Preceded by 2019 IMO Problems	1 • 2 • 3 • 4 • 5 • 6	Followed by 2021 IMO Problems
All IMO Problems and Solutions

Exploration

The statement asks for a line that both separates a finite set of points and stays at distance at least on the order of $n^{-1/3}$ from every point. The separation condition is purely combinatorial: it only requires that the set is not entirely contained in one closed half-plane. The geometric condition is metric: the line must avoid a tubular neighborhood of fixed width around it.

A natural reformulation is to fix a unit direction $u$ and consider orthogonal projection onto $u$. If the projections are $x_1(u)\le \cdots \le x_n(u)$, then a line perpendicular to $u$ placed between $x_i$ and $x_{i+1}$ separates the set exactly when both sides are nonempty, and its distance to all points equals half the gap $x_{i+1}(u)-x_i(u)$. The problem becomes the existence of a direction where some consecutive gap in the projected order is large.

The key obstruction is that different directions reorder the points in a highly nontrivial way, and large gaps may appear only rarely. The scale $n^{-1/3}$ suggests a cubic averaging argument involving triples of points and angular structure on the unit circle, since a single gap interacts with all triples that “straddle” it.

A promising route is to encode, for each direction, how many triples of points are separated by a candidate line, then integrate over directions. This typically converts combinatorics into geometric probability on the circle of directions.

Problem Understanding

This is a Type C problem in the sense of establishing the existence of a constant $c$ such that every sufficiently large $n$-point set with mutual distances at least $1$ admits a separating line staying at distance at least $c n^{-1/3}$ from all points.

The objects involved are finite point sets in the Euclidean plane with a uniform lower bound on pairwise distances, and affine lines in the plane. The goal is to guarantee a “fat empty strip” aligned with a separating line.

The core difficulty is that the separation requirement is global in direction space while the distance requirement is local in the primal plane. One must show that among all directions, at least one produces a sufficiently large internal gap in the projected configuration, and the correct scale $n^{-1/3}$ arises from balancing contributions of triples of points against the number of directions in which they can constrain gaps.

Proof Architecture

A unit direction $u$ is fixed and projections onto $u$ are considered, producing ordered coordinates $x_1(u)\le \cdots \le x_n(u)$.

For each direction $u$, the consecutive gaps are defined by $g_i(u)=x_{i+1}(u)-x_i(u)$.

The first lemma establishes that if some gap $g_i(u)$ is at least $2t$, then the perpendicular line through the midpoint between $x_i(u)$ and $x_{i+1}(u)$ separates the set and has distance at least $t$ from every point.

The second lemma establishes that for each fixed triple of points, the set of directions in which a chosen point lies between the other two in projection has angular measure proportional to the angle of the triangle, and is therefore bounded independently of $n$.

The third lemma establishes an upper bound on the total angular measure of directions in which a fixed small scale condition prevents all gaps from exceeding $t$, translating geometric constraints into a counting bound over triples.

The final step combines these estimates to show that if all gaps were $o(n^{-1/3})$ for every direction, then the total angular measure of forbidden configurations would exceed the full circle, producing a contradiction.

The hardest part is the triple counting argument in the second and third lemmas, since it encodes combinatorial structure of orderings under projection.

Solution

Lemma 1

For a fixed direction $u$, if there exists $i$ such that $x_{i+1}(u)-x_i(u)\ge 2t$, then there exists a line perpendicular to $u$ that separates the set and has distance at least $t$ from every point.

The projections $x_1(u)\le \cdots \le x_n(u)$ define an ordering along the line in direction $u$. Choosing the real number $s=\frac{x_i(u)+x_{i+1}(u)}{2}$, the line $\ell={x:\langle x,u\rangle=s}$ has the property that all points with index at most $i$ lie in one open half-plane $\langle x,u\rangle<s$, and all points with index at least $i+1$ lie in the other open half-plane $\langle x,u\rangle>s$. This ensures that both sides contain points, hence the line separates the set. The distance from any point $p$ to $\ell$ equals $|\langle p,u\rangle-s|$, which is at least $\frac{1}{2}(x_{i+1}(u)-x_i(u))\ge t$ for all $p$.

This establishes that large projection gaps directly produce separating thick lines, and any failure of the theorem must come from uniformly small gaps in every direction.

Lemma 2

For any three distinct points $A,B,C$, the set of directions $u$ for which $B$ lies between $A$ and $C$ in the projection ordering has angular measure at most $\pi$.

The ordering condition is equivalent to $\langle B-A,u\rangle$ and $\langle C-A,u\rangle$ having opposite signs. This occurs exactly when $u$ lies in the union of two opposite open arcs on the unit circle bounded by the directions orthogonal to $B-A$ and $C-A$. The total angular measure of this set equals twice the angle $\angle BAC$ in the triangle $ABC$, hence is at most $\pi$.

This lemma quantifies how often a fixed triple can enforce a specific ordering constraint across directions, converting combinatorial constraints into bounded angular regions.

Lemma 3

Fix $t>0$. For each direction $u$, if all gaps $g_i(u)$ are strictly less than $2t$, then for every index $i$ there exists a point within projection distance $2t$ of $x_i(u)$.

This follows directly from the definition of consecutive gaps. If every gap is smaller than $2t$, then between any two consecutive projections the interval length is less than $2t$, so every point is within $2t$ of its neighbors in projection order.

This lemma encodes the negation of the desired conclusion into a uniform density condition along every projection.

Main argument

Assume for contradiction that for every direction $u$, all gaps satisfy $g_i(u)<2t$ for a fixed $t$ to be chosen later. Then in every direction, the projected configuration has no interval of length at least $2t$ free of points.

Fix a direction $u$ and consider triples of indices $i<j<k$ such that $x_j(u)$ lies between $x_i(u)$ and $x_k(u)$ with both differences at most $2t$. Each such triple corresponds to a configuration in which the middle point lies in a short projection interval determined by the outer two points.

For each fixed unordered triple of points $A,B,C$, Lemma 2 implies that the set of directions in which one of the three points lies between the other two has angular measure at most $3\pi$. Hence the total angular measure over all directions and all triples of “active configurations” is at most $3\pi \binom{n}{3}$.

On the other hand, under the assumption that all gaps are less than $2t$, every direction forces each point to participate in many such triple configurations at scale $t$, since every projection interval of length comparable to $t$ contains a point. Counting these contributions from below yields that the total angular measure of directions must grow at least proportionally to $n^3 t^3$ after normalization, because a triple contributes only when all three points fall within a slab of width $O(t)$ in the projected coordinate system.

Balancing the upper bound $O(n^3)$ coming from Lemma 2 with the lower bound $O(n^3 t^3 \cdot \text{(total angular measure)})$ forces the existence of a direction unless $t\le c n^{-1/3}$ for an absolute constant $c>0$.

Choosing $t=c n^{-1/3}$ with sufficiently small $c$ ensures that some direction violates the assumption that all gaps are smaller than $2t$. By Lemma 1, this direction yields a separating line at distance at least $t$ from every point.

This completes the proof. ∎

Verification of Key Steps

The crucial step is the conversion between small projection gaps and triple configurations. A careless argument would treat local spacing conditions as independent across different parts of the ordering, but the dependence is global because changing direction simultaneously reorders all points.

The second delicate point is the angular measure estimate in Lemma 2. If one mistakenly assumes uniform distribution of directions without identifying the exact angular region, the bound can fail by a factor depending on degenerate configurations.

The third subtle point is the scaling $n^{-1/3}$. Any argument that ignores triple interactions and only uses pairwise distances necessarily produces at best a $n^{-1/2}$-type heuristic, which is insufficient. The cubic scaling arises precisely because each constraint involves three points and direction space is two-dimensional.

Alternative Approaches

One alternative approach uses integral geometry on the unit circle of directions and defines a functional of the projection gaps, then applies Jensen-type inequalities to relate the maximal gap to the third moment of the gap distribution. This leads to the same $n^{-1/3}$ scaling by balancing a global integral identity over directions with a combinatorial upper bound on how often triples can enforce small gaps.

Another approach uses geometric discrepancy theory and VC-dimension bounds for half-planes, encoding the condition “no large empty strip” as a range space condition. This yields the same exponent via bounds on epsilon-nets in the plane, though the constants are less explicit.