← All resources

combinatoiregéométrie prépa IMO2020imo

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