\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{IMO 2020/6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 30}
\maketitle
\section*{Problem}
Consider an integer $n > 1$, and a set $\mathcal S$ of $n$ points
in the plane such that the distance between any two different points
in $\mathcal S$ is at least $1$.
Prove there is a line $\ell$ separating $\mathcal S$
such that the distance from any point of $\mathcal S$ to $\ell$
is at least $\Omega(n^{-1/3})$.
(A line $\ell$ separates a set of points $S$
if some segment joining two points in $\mathcal S$ crosses $\ell$.)
\section*{Video}
\href{https://www.youtube.com/watch?v=JfRrlvbzKHk}{\texttt{https://youtu.be/OxeeSsdEgwI}}
\newpage
\section*{Solution}
We present the official solution given by the Problem Selection Committee.
Let's suppose that among all projections
of points in $\mathcal S$ onto some line $m$,
the maximum possible distance between two consecutive projections is $\delta$.
We will prove that $\delta \ge \Omega(n^{-1/3})$,
solving the problem.
We make the following the definitions:
\begin{itemize}
\ii Define $A$ and $B$ as the two points farthest apart in $\mathcal S$.
This means that all points lie in the intersections
of the circles centered at $A$ and $B$ with radius $R = AB \ge 1$.
\ii We pick chord $\ol{XY}$ of $\odot(B)$
such that $\ol{XY} \perp \ol{AB}$ and the distance
from $A$ to $\ol{XY}$ is exactly $\half$.
\ii We denote by $\mathcal T$
the smaller region bound by $\odot(B)$ and chord $\ol{XY}$.
\end{itemize}
The figure is shown below with $\mathcal T$ drawn in yellow,
and points of $\mathcal S$ drawn in blue.
\begin{center}
\begin{asy}
size(10cm);
pair A = (-2,0);
pair B = (5,0);
pen auxpen = brown+linetype("4 2");
pair X = (0, 24^0.5);
pair Y = (0, -24^0.5);
pair[] S = {
(-1.3, 2.7),
(-0.57, -2.61),
(-0.21, 1.07),
(0.33,-1.06),
(0.83, 3.71),
(1.57, -3.18),
(2.14, 1.66),
(2.72, 3.32),
(3.37, -1.17),
(3.97, 1.34),
(4.37, -2.35),
};
fill(Y..A..X--cycle, paleyellow);
for (int i=0; i \frac{\sqrt3}{2} \left( \half \delta\inv - 1 \right)$.
\end{claim*}
\begin{proof}
Because $\mathcal T$ is so narrow (has width $\half$ only),
the projections of points in $\mathcal T$ onto line $XY$
are spaced at least $\frac{\sqrt3}{2}$ apart (more than just $\delta$).
This means
\[ XY > \frac{\sqrt3}{2}
\left( \left\lvert \mathcal T \right\rvert - 1 \right). \]
But projections of points in $\mathcal T$
onto the segment of length $\half$ are spaced at most $\delta$ apart,
so apparently
\[ \left\lvert \mathcal T \right\rvert > \half \cdot \delta\inv. \]
This implies the result.
\end{proof}
Combining these two this implies $\delta \ge \Omega(n^{-1/3})$ as needed.
\begin{remark*}
The constant $1/3$ in the problem is actually optimal
and cannot be improved;
the constructions give an example showing $\Theta(n^{-1/3} \log n)$.
\end{remark*}
\end{document}