Shortlist 2020, G9¶
Domaine : Géométrie · Difficulté : ★★★★★ · Proposé par : Taiwan
Concepts : Principe extrémal · Géométrie combinatoire : enveloppe convexe, points du réseau
Solution officielle : Shortlist officielle 2020 (avec solutions), p. 67 (page 69 du PDF)
Problème 6 de l'OIM 2020
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2020, où il était le problème 6 (jour 2).
Figures reprises du livret officiel de la Shortlist.
Énoncé¶
Montrer qu'il existe une constante \(c\) strictement positive telle que l'énoncé suivant soit vrai :
Soit \(n \geq 2\) un entier, et soit \(\mathcal{S}\) un ensemble de \(n\) points du plan tels que la distance entre deux points distincts quelconques de \(\mathcal{S}\) soit au moins \(1\). Alors il existe une droite \(\ell\) séparant \(\mathcal{S}\) telle que la distance de tout point de \(\mathcal{S}\) à \(\ell\) soit au moins \(c\, n^{-1/3}\).
(Une droite \(\ell\) sépare un ensemble de points \(\mathcal{S}\) si un segment joignant deux points de \(\mathcal{S}\) coupe \(\ell\).)
Énoncé original (anglais)
Prove that there exists a positive constant \(c\) such that the following statement is true:
Assume that \(n\) is an integer with \(n \geq 2\), and let \(\mathcal{S}\) be a set of \(n\) points in the plane such that the distance between any two distinct points in \(\mathcal{S}\) is at least \(1\). Then there is a line \(\ell\) separating \(\mathcal{S}\) such that the distance from any point of \(\mathcal{S}\) to \(\ell\) is at least \(c\, n^{-1/3}\).
(A line \(\ell\) separates a point set \(\mathcal{S}\) if some segment joining two points in \(\mathcal{S}\) crosses \(\ell\).)
Indices : les idées clés
- Projeter sur une droite : si deux projetés consécutifs sont à distance \(2d\), la perpendiculaire passant par leur milieu sépare \(\mathcal{S}\) à distance au moins \(d\) de tous les points ; on suppose par l'absurde que tous les écarts sont \(< 2\delta\).
- Principe extrémal : on projette sur la droite \(AB\), où \([AB]\) est un diamètre de \(\mathcal{S}\) (distance maximale), ce qui contient \(\mathcal{S}\) dans deux disques.
- Géométrie combinatoire : enveloppe convexe, points du réseau : dans une bande étroite au bord de \(\mathcal{S}\), compter les points de deux façons (minoration par les petits écarts, majoration par la largeur du segment circulaire) et faire jouer les trois estimations.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2020 (une solution et deux remarques).
Solution¶

Montrons que l'énoncé est vrai avec \(c = \frac{1}{8}\). Posons \(\delta = \frac{1}{8} n^{-1/3}\). Pour toute droite \(\ell\) et tout point \(X\), notons \(X_\ell\) le projeté orthogonal de \(X\) sur \(\ell\) ; même notation pour les ensembles de points.
Supposons que, pour une certaine droite \(\ell\), l'ensemble \(\mathcal{S}_\ell\) contienne deux points consécutifs \(X\) et \(Y\) avec \(XY = 2d\). Alors la droite perpendiculaire à \(\ell\) passant par le milieu de \([XY]\) sépare \(\mathcal{S}\), et tous les points de \(\mathcal{S}\) sont à distance au moins \(d\) de cette droite. Donc, si \(d \geq \delta\), on a trouvé une droite convenable. Supposons par l'absurde que ce n'est jamais le cas, quelle que soit la projection.
Selon le principe extrémal, choisissons deux points \(A\) et \(B\) de \(\mathcal{S}\) à distance maximale \(M = AB\) (\([AB]\) est un diamètre de \(\mathcal{S}\)) ; par hypothèse, \(M \geq 1\). Notons \(\ell\) la droite \(AB\). L'ensemble \(\mathcal{S}\) est contenu dans l'intersection des disques \(D_A\) et \(D_B\) de rayon \(M\) centrés en \(A\) et \(B\). Donc la projection \(\mathcal{S}_\ell\) est contenue dans le segment \([AB]\). De plus, les points de \(\mathcal{S}_\ell\) découpent ce segment en au plus \(n - 1\) morceaux, chacun de longueur strictement inférieure à \(2\delta\). Par conséquent,
Soit \(H\) le point de \([AB]\) tel que \(AH = \frac{1}{2}\). Soit \(P\) la bande comprise entre les droites \(a\) et \(h\) perpendiculaires à \(AB\) passant respectivement par \(A\) et \(H\) (bords compris). Posons \(\mathcal{T} = P \cap \mathcal{S}\) et \(t = |\mathcal{T}|\). D'après notre hypothèse, le segment \([AH]\) contient au moins \(\left\lceil \frac{1}{2} : (2\delta) \right\rceil\) points de \(\mathcal{S}_\ell\), d'où
Remarquons que \(\mathcal{T}\) est contenu dans \(Q = P \cap D_B\). L'ensemble \(Q\) est un segment circulaire, dont la projection \(Q_a\) est un segment de longueur
D'autre part, pour deux points \(X, Y \in \mathcal{T}\), on a \(XY \geq 1\) et \(X_\ell Y_\ell \leq \frac{1}{2}\), donc
En résumé, les \(t\) points de \(\mathcal{T}_a\) sont sur un segment de longueur inférieure à \(2\sqrt{M}\), deux à deux distants d'au moins \(\frac{\sqrt{3}}{2}\). Donc \(2\sqrt{M} > (t - 1)\frac{\sqrt{3}}{2}\), soit
car \(M \geq 1\).
En combinant (1), (2) et (3), on obtient finalement
ce qui est faux pour la valeur choisie de \(\delta\) (on a \(512\, n\delta^3 = 1\)). Cette contradiction montre que \(c = \frac{1}{8}\) convient. \(\blacksquare\)
Remarques¶

Remarque 1. Comme l'indique l'auteur du problème, l'exposant \(-1/3\) est optimal : pour tout \(n \geq 2\), il existe une configuration \(\mathcal{S}\) de \(n\) points deux à deux distants d'au moins \(1\) telle que toute droite séparant \(\mathcal{S}\) est à distance au plus \(c' n^{-1/3} \log n\) d'un point de \(\mathcal{S}\), où \(c'\) est une constante absolue.
La proposition originale demandait une estimation de la forme \(c n^{-1/2}\), qui admet des solutions bien plus simples. Par exemple, avec \(\delta = \frac{1}{16} n^{-1/2}\), l'inégalité (1) montre que \(\mathcal{S}\) est contenu dans un disque \(D\) de rayon \(\frac{1}{8} n^{1/2}\). D'autre part, les disques \(D_X\) de rayon \(\frac{1}{2}\) centrés aux points \(X\) de \(\mathcal{S}\) ont des intérieurs disjoints et sont contenus dans le disque concentrique à \(D\) de rayon \(\frac{1}{8} n^{1/2} + \frac{1}{2}\). En comparant les aires,
ce qui est absurde (la dernière inégalité, \(\frac{n}{64} + \frac{\sqrt{n}}{8} + \frac{1}{4} < \frac{n}{4}\), est vraie pour tout \(n \geq 2\)). (Le livret écrit ici le rayon \(\frac{1}{16} n^{1/2} + \frac{1}{2}\), incohérent avec le rayon \(\frac{1}{8} n^{1/2}\) annoncé juste avant ; le calcul ci-dessus utilise ce dernier et la conclusion subsiste.) Le comité de sélection a préféré retenir la version plus difficile.
Remarque 2 (variantes sans le diamètre). Posons \(\delta = c n^{-1/3}\) pour une constante \(c > 0\) assez petite, et supposons par l'absurde qu'aucune droite séparante n'est à distance au moins \(\delta\) de tous les points de \(\mathcal{S}\). Soit \(C\) l'enveloppe convexe de \(\mathcal{S}\) ; une droite est séparante si et seulement si elle rencontre \(C\) (une droite passant par un point de \(\mathcal{S}\) est considérée comme séparante). Pour une bande entre deux droites séparantes parallèles \(a\) et \(a'\) distantes de \(\frac{1}{4}\), on appelle tranche l'intersection de \(\mathcal{S}\) avec la bande, et longueur de la tranche le diamètre de sa projection sur \(a\). Les arguments prouvant (2) et (3) montrent que pour toute tranche \(\mathcal{T}\) de longueur \(L\),
L'idée clé est d'appliquer ces estimations à une tranche de bord, pour laquelle \(a\) ne traverse pas l'intérieur de \(C\) ; la solution ci-dessus le fait pour une tranche bien choisie, on peut aussi en utiliser beaucoup (\(n\) étant supposé assez grand). On oriente \(a\) de sorte que \(C\) soit à sa gauche ; \(a\) est la droite d'appui et cette orientation la direction de la tranche, qui la détermine. On fixe une direction \(\mathbf{v}_0\) et, pour \(\alpha \in [0, 2\pi)\), on note \(\mathcal{T}_\alpha\) la tranche de bord de direction \(\mathbf{v}_0\) tournée de \(\alpha\). En orientant la figure de bas en haut selon la direction, on définit la moitié haute \(\mathsf{T}(\mathcal{T})\) (les \(\lfloor |\mathcal{T}|/2 \rfloor\) points les plus hauts) et la moitié basse \(\mathsf{B}(\mathcal{T})\) ; par (4), chacune contient au moins \(10\) points.
Affirmation. Si \(\alpha, \beta \in [0, \pi/2]\) avec \(\beta - \alpha \geq 40\delta =: \phi\), alors les points communs à \(\mathcal{T}_\alpha\) et \(\mathcal{T}_\beta\) sont dans \(\mathsf{T}(\mathcal{T}_\alpha) \cap \mathsf{B}(\mathcal{T}_\beta)\).
Idée de preuve. Par symétrie, il suffit de montrer qu'ils sont dans \(\mathsf{T}(\mathcal{T}_\alpha)\). Soient \(P_1, \ldots, P_k\) les points de \(\mathcal{T}_\alpha\) de bas en haut ; par (4), \(k \geq \frac{1}{8}\delta^{-1}\). Dans un repère où la droite d'appui de \(\mathcal{T}_\alpha\) est l'axe des ordonnées, pour \(P_i \in \mathsf{B}(\mathcal{T}_\alpha)\), les ordonnées de \(P_k\) et \(P_i\) diffèrent d'au moins \(\frac{\sqrt{15}}{4}(k - i) > \frac{1}{3}k\) et leurs abscisses d'au plus \(\frac{1}{4}\). Leurs projetés sur une droite \(\ell\) perpendiculaire à la direction de \(\mathcal{T}_\beta\) sont donc distants d'au moins
et \(P_k\) est plus proche que \(P_i\) de la droite d'appui de \(\mathcal{T}_\beta\) ; donc \(P_i \notin \mathcal{T}_\beta\).
On pose alors \(\alpha_i = 40\delta i\) pour \(i = 0, 1, \ldots, \left\lfloor \frac{1}{40}\delta^{-1} \cdot \frac{\pi}{2} \right\rfloor\). D'après l'affirmation, chaque point de \(\mathcal{S}\) est dans au plus deux tranches \(\mathcal{T}_{\alpha_i}\), donc leur réunion \(\mathcal{U}\) contient au moins \(\frac{1}{2} \cdot \frac{1}{8\delta} \cdot \frac{1}{40\delta} \cdot \frac{\pi}{2} = \frac{\lambda}{\delta^2}\) points (pour une constante \(\lambda\)), chacun à distance au plus \(\frac{1}{4}\) du bord de \(C\). On aboutit alors à une contradiction avec (1) : par exemple, si \(f(X)\) est un point du bord de \(C\) le plus proche de \(X \in \mathcal{U}\), on a \(f(X)f(Y) \geq XY - \frac{1}{2} \geq \frac{1}{2} XY\), donc le périmètre de \(C\), et par suite le diamètre de \(\mathcal{S}\), est au moins de l'ordre de \(\mu\delta^{-2}\). On peut aussi montrer que la projection de \(\mathcal{U}\) sur la droite faisant un angle \(\pi/4\) avec \(\mathbf{v}_0\) a un diamètre au moins \(\mu\delta^{-2}\).
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2014 C5 ★★★☆☆ · OIM P6 : Parmi \(n\) droites, on peut en colorier \(\lceil \sqrt{n/2} \rceil\) en bleu sans qu'aucune région bornée ait un bord tout bleu.
- 2021 G6 ★★★★☆ : Pour quels \(n\) tout \(n\)-gone convexe de côtés \(1\) contient-il un triangle équilatéral de côté \(1\) ?
- 2024 A8 ★★★★★ : Trouver les suites dont toute fenêtre de \(p + 1\) termes a un écart \(p\), et toute fenêtre de \(q + 1\) termes un écart \(q\).
- 2015 G8 ★★★★★ : Deux triangulations d'un polygone en triangles de même aire ne diffèrent que par deux triangles.