Shortlist 2008, G5¶
Domaine : Géométrie · Difficulté : ★★★☆☆ · Proposé par : non indiqué
Concepts : Géométrie combinatoire : enveloppe convexe, points du réseau · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2008 (avec solutions), p. 36 (page 37 du PDF)
Figures reprises du livret officiel de la Shortlist.
Énoncé¶
Soient \(k\) et \(n\) des entiers avec \(0 \leq k \leq n - 2\). On considère un ensemble \(L\) de \(n\) droites du plan, deux d'entre elles n'étant jamais parallèles et trois n'ayant jamais de point commun. On note \(I\) l'ensemble des points d'intersection des droites de \(L\). Soit \(O\) un point du plan qui n'est sur aucune droite de \(L\).
Un point \(X \in I\) est colorié en rouge si le segment ouvert \(OX\) coupe au plus \(k\) droites de \(L\). Montrer que \(I\) contient au moins \(\frac{1}{2}(k + 1)(k + 2)\) points rouges.
Énoncé original (anglais)
Let \(k\) and \(n\) be integers with \(0 \leq k \leq n - 2\). Consider a set \(L\) of \(n\) lines in the plane such that no two of them are parallel and no three have a common point. Denote by \(I\) the set of intersection points of lines in \(L\). Let \(O\) be a point in the plane not lying on any line of \(L\).
A point \(X \in I\) is colored red if the open line segment \(OX\) intersects at most \(k\) lines in \(L\). Prove that \(I\) contains at least \(\frac{1}{2}(k + 1)(k + 2)\) red points.
Indices : les idées clés
- Ordre d'un point : le nombre de droites coupant le segment ouvert \(OP\) ; un coin de la région contenant \(O\) est d'ordre \(0\).
- Lemme (géométrie combinatoire) : deux points consécutifs d'une même droite ont des ordres qui diffèrent d'au plus \(1\) (considérer le triangle \(OPQ\)).
- Récurrence sur \(k\) : sur une droite passant par un point d'ordre \(0\), les \(k\) points les plus proches sont d'ordre \(\leq k\) ; on retire la droite et l'on applique l'hypothèse de récurrence.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2008 (une solution et une remarque).
Solution¶
Il y a au moins \(\frac{1}{2}(k + 1)(k + 2)\) points dans l'ensemble d'intersection \(I\), vu la condition \(n \geq k + 2\).
Pour chaque point \(P \in I\), définissons son ordre comme le nombre de droites qui coupent le segment ouvert \(OP\). Par définition, \(P\) est rouge si son ordre est au plus \(k\). Remarquons qu'il existe toujours au moins un point \(X \in I\) d'ordre \(0\). En effet, les droites de \(L\) découpent le plan en régions, bornées ou non, et \(O\) appartient à l'une d'elles. Tout coin de cette région est évidemment un point de \(I\) d'ordre \(0\).
Affirmation. Supposons que deux points \(P, Q \in I\) soient sur une même droite de \(L\), et qu'aucune autre droite de \(L\) ne coupe le segment ouvert \(PQ\). Alors les ordres de \(P\) et de \(Q\) diffèrent d'au plus \(1\).
Preuve. Soient \(p\) et \(q\) les ordres de \(P\) et \(Q\), avec \(p \geq q\). Considérons le triangle \(OPQ\). Alors \(p\) est le nombre de droites de \(L\) qui coupent l'intérieur du côté \(OP\). Aucune de ces droites ne coupe l'intérieur du côté \(PQ\), et au plus une peut passer par \(Q\). Toutes les autres droites doivent couper l'intérieur du côté \(OQ\), ce qui implique \(q \geq p - 1\). La conclusion en découle. \(\square\)
Prouvons le résultat principal par récurrence sur \(k\). Le cas de base \(k = 0\) est clair, puisqu'il existe un point d'ordre \(0\), qui est rouge. Supposons l'énoncé vrai pour \(k - 1\) et passons à l'hérédité. Choisissons un point \(P \in I\) d'ordre \(0\), et considérons l'une des droites \(\ell \in L\) passant par \(P\). Il y a \(n - 1\) points d'intersection sur \(\ell\), dont \(P\). Parmi les \(n - 2\) autres, les \(k\) plus proches de \(P\) ont des ordres au plus égaux à \(k\), d'après l'affirmation. Il s'ensuit qu'il y a au moins \(k + 1\) points rouges sur \(\ell\).
Considérons maintenant la situation où \(\ell\) est retirée (avec tous les points d'intersection qu'elle contient). D'après l'hypothèse de récurrence, il y a au moins \(\frac{1}{2}k(k + 1)\) points d'ordre au plus \(k - 1\) dans la configuration obtenue. Remettre \(\ell\) ajoute au plus un nouveau point d'intersection sur chaque segment joignant l'un de ces points à \(O\), de sorte que leur ordre est au plus \(k\) dans la configuration initiale. Le nombre total de points d'ordre au plus \(k\) est donc au moins \((k + 1) + \frac{1}{2}k(k + 1) = \frac{1}{2}(k + 1)(k + 2)\). Cela termine la preuve. \(\blacksquare\)
Remarque¶
On peut suivre les étapes de la preuve en sens inverse pour obtenir une configuration de \(n\) droites dans laquelle l'égalité a lieu simultanément pour tous les \(0 \leq k \leq n - 2\). Un tel ensemble de droites est représenté sur la figure.

Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2019 C4 ★★☆☆☆ : Un labyrinthe de droites peintes, des portes aux intersections : combien de chevaliers isolés Morgane peut-elle placer ?
- 2006 C2 ★★☆☆☆ · OIM P2 : Une triangulation d'un \(2006\)-gone régulier : combien de triangles isocèles à deux côtés impairs au maximum ?
- 2019 C6 ★★★☆☆ : Ordonner \(2n\) points pour que les angles du polygone obtenu se répartissent en deux groupes de même somme.
- 2016 C5 ★★★☆☆ : Combien de diagonales d'un \(n\)-gone régulier peut-on choisir pour que deux qui se coupent soient perpendiculaires ?