← Toutes les ressources

combinatoiregéométrie prépa IMO2020imo

Une droite qui sépare le nuage de points

IMO · 2020 · Russie ·

Énoncé

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$.

Aperçu rendu par KaTeX — la mise en page exacte est celle du PDF compilé.

Source & crédits

Origine : IMO 2020, Problème 6 — voir la source originale

Énoncés officiels © IMO (imo-official.org), reproduits à des fins pédagogiques avec attribution.

Téléchargements

Les PDF sont générés par le pipeline GitHub Actions : ils peuvent être absents en développement local.

+ Ajouter au sujet