Международная олимпиада 2020, Санкт-Петербург, Россия, 2020 год


Докажите, что существует положительная константа $c$, для которой выполняется следующее утверждение:  Пусть $S$ — множество из $n > 1$ точек плоскости, в котором расстояние между любыми двумя точками не меньше 1.
Тогда существует прямая $\ell$, разделяющая множество $S$, такая что расстояние от любой точки $S$ до $\ell$ не меньше чем $cn^{-1/3}.$
(Прямая $\ell$ разделяет множество точек $S$, если она пересекает некоторый отрезок, концы которого принадлежат $S$.)
Замечание. Более слабые результаты с заменой $cn^{-1/3}$ на $cn^{-\alpha}$ могут оцениваться в зависимости от значения константы $\alpha > 1/3$.
посмотреть в олимпиаде

Комментарий/решение: