A line separating the point cloud
IMO · 2020 · Russie · ★★★★★
Statement
Montrer qu'il existe une constante strictement positive $c$ telle que l'assertion suivante soit vraie :
Considérons un entier $n > 1$, et un ensemble $S$ de $n$ points du plan tel que la distance entre deux points distincts dans $S$ soit toujours au moins égale à $1$. Alors il existe une droite $\ell$ qui sépare $S$, de sorte que la distance de n'importe quel point de $S$ à $\ell$ vaut au moins $c\, n^{-1/3}$.
(On dit qu'une droite $\ell$ sépare un ensemble de points $S$ lorsque $\ell$ rencontre au moins un segment joignant deux points de $S$.)
Remarque. Des résultats plus faibles avec $c\, n^{-\alpha}$ à la place de $c\, n^{-1/3}$ pourront recevoir des points selon la valeur de la constante $\alpha > 1/3$.
Preview rendered with KaTeX — the compiled PDF is the reference layout.
Source & credits
Origin : IMO 2020, Problème 6 — view the original source
Énoncés officiels © IMO (imo-official.org), reproduits à des fins pédagogiques avec attribution.
Downloads
PDFs are produced by the GitHub Actions pipeline: they may be missing in local development.
+ Add to problem set


