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é

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.