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.
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
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}\).