2020 IMO SL #G9

Prove that there exists a positive constant $c$ such that the following statement is true: 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. It follows that there is a line $\ell$ separating $\mathcal S$ such that the distance from any point of $\mathcal 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 $\mathcal S$ crosses $\ell$.)

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 need to prove $\delta \ge \Omega(n^{-1/3})$. 

At this point, define $A,B$ as the two farthest points in $\mathcal{S}$. So, all points lie in the intersections of the circles centered at $A,B$ with radius $AB \geq 1$.  Choose chord $XY$ in circle $B$ where $XY \perp AB$ and $d(A, XY)=\frac{1}{2}$. Also, let $\mathcal{T}$ be the smaller region which is bounded by circle $B$ and chord $XY$. 

We try to bring the radius into play. Note $R=AB<(n-1)\cdot\delta$, since the $n$ projections of points onto $AB$ are spaced at most $\delta$ apart. Then, the Pythagorean Theorem gives us $$XY=2\sqrt{R^2-(R-\frac{1}{2})^2=2\sqrt{R-\frac{1}{4}}}<2\sqrt{n\delta},$$
so we deduce $XY < 2 \sqrt{n\delta}$. 

Now, since $\mathcal{T}$ has width of only $\frac{1}{2}$, the projections of points contained in $\mathcal{T}$ on $\overline{XY}$ are at least $\frac{\sqrt{3}}{2}$ apart. So, $$XY>\frac{\sqrt{3}}{2}(|\mathcal{T}|-1).$$
However, projections of points in $\mathcal{T}$ onto the segment with length $\frac{1}{2}$ are at maximum $\delta$ apart, so we must have $$|\mathcal{T}|>\frac{1}{2} \cdot \delta^{-1}.$$
So, we can also say that $$XY>\frac{\sqrt{3}}{2}\left( \frac{1}{2}\delta^{-1}-1 \right).$$ 
Combining $XY<2\sqrt{n\delta}$ and the result above gives us the desired $\delta \geq \Omega(n^{-1/3})$. $\square$ 


  1. Anonymous1/20/2022


    2020 imo #6
    very hard problem

    most solutions online are very bashy
    urs is very elegant :)

    nice job


Post a Comment

Popular posts from this blog

1995 IMO #2

2014 IMO SL #C2

2015 IMO SL #A1