Aller au contenu

Géométrie combinatoire : enveloppe convexe, points du réseau

Domaine : Combinatoire · Niveau : intermédiaire · Prérequis : Principe extrémal

L'idée

La géométrie combinatoire étudie des configurations finies de points, de droites, de segments ou de polygones : combien de régions, quels points sont « au bord », peut-on relier ou séparer des points sans croisement ? On utilise peu de calcul et beaucoup de positions relatives.

Quelques outils reviennent sans cesse.

  • L'enveloppe convexe d'un ensemble fini de points est le plus petit polygone convexe qui les contient. Ses sommets sont des points de l'ensemble ; par un tel sommet passe une droite qui laisse tous les autres points du même côté. C'est la version géométrique du principe extrémal : le point le plus à gauche, le plus bas, est toujours un sommet de l'enveloppe.
  • Balayer avec une droite. On fait glisser ou tourner une droite, dans une direction qui n'est parallèle à aucune droite passant par deux points. Elle ne rencontre alors les points qu'un par un, ce qui permet de séparer l'ensemble en deux groupes de tailles choisies.
  • L'inégalité triangulaire et les aires. Deux segments qui se croisent sont plus longs que les deux segments « décroisés » ; des triangles sans point intérieur commun ont une aire totale bornée.
  • Compter. Les régions découpées par des droites, les points d'intersection, avec la formule d'Euler \(S - A + F = 2\) (voir Graphes).

Points du réseau

Un point du réseau est un point à coordonnées entières.

  • Parités. Il n'y a que \(4\) classes de parité \((x \bmod 2, y \bmod 2)\). Deux points de la même classe ont un milieu à coordonnées entières (principe des tiroirs).
  • Points sur un segment. Le segment de \((0, 0)\) à \((a, b)\) contient exactement \(\operatorname{pgcd}(a, b) + 1\) points du réseau.
  • Formule de Pick. Un polygone dont les sommets sont des points du réseau, avec \(I\) points du réseau à l'intérieur et \(B\) sur le bord, a pour aire \(I + \frac{B}{2} - 1\).

Exemple résolu

Problème

On donne \(n\) points rouges et \(n\) points bleus dans le plan, trois jamais alignés. Montrer qu'on peut relier chaque point rouge à un point bleu par \(n\) segments deux à deux disjoints.

Étape 1 : choisir l'objet extrémal. Il y a un nombre fini de façons d'associer les rouges aux bleus (\(n!\)). On choisit celle dont la somme des longueurs des \(n\) segments est minimale.

Étape 2 : supposer un croisement. Supposons que deux segments \(R_1B_1\) et \(R_2B_2\) de cette association se coupent en un point \(X\).

Étape 3 : décroiser. Remplaçons-les par \(R_1B_2\) et \(R_2B_1\). Par l'inégalité triangulaire, stricte car les points ne sont pas alignés :

\[R_1B_2 + R_2B_1 < (R_1X + XB_2) + (R_2X + XB_1) = R_1B_1 + R_2B_2.\]

La nouvelle association a une longueur totale strictement plus petite, ce qui contredit le choix de l'étape 1.

Conclusion. L'association de longueur minimale n'a aucun croisement.

L'idée géométrique, « deux segments croisés sont plus longs que les segments décroisés », se combine ici avec le principe extrémal. Ce couple revient très souvent.

Comment le reconnaître

  • L'énoncé parle d'un ensemble fini de points (souvent « trois jamais alignés »), de droites ou de segments, et pose une question d'existence ou de dénombrement.
  • On veut séparer des points par une droite, ou les relier sans croisement.
  • L'énoncé parle de convexité, de polygones convexes, de points « à l'intérieur ».
  • Il y a des coordonnées entières : points du réseau, quadrillage, aires de polygones à sommets entiers.

Techniques classiques

Situation Technique
Ensemble fini de points Regarder l'enveloppe convexe, ou le point le plus à gauche
Séparer en deux groupes Faire glisser ou tourner une droite de direction générique
Relier sans croisement Minimiser la longueur totale et décroiser
Points du réseau Classes de parité, PGCD pour les points d'un segment, formule de Pick
Régions, intersections Compter sommets, arêtes et faces ; formule d'Euler
Beaucoup de figures disjointes dans une zone Argument d'aire ou de périmètre

Exercices d'échauffement

  1. On choisit \(5\) points du réseau. Montrer que deux d'entre eux ont un milieu à coordonnées entières.
  2. Combien de points du réseau le segment de \((0, 0)\) à \((12, 18)\) contient-il ?
  3. Montrer qu'un triangle dont les sommets sont des points du réseau, et qui ne contient aucun autre point du réseau (ni à l'intérieur, ni sur les côtés), a une aire égale à \(\frac{1}{2}\).
  4. On donne \(5\) points du plan, trois jamais alignés. Montrer que \(4\) d'entre eux sont les sommets d'un quadrilatère convexe. Indication : distinguer selon le nombre de sommets de l'enveloppe convexe.
  5. On donne \(2n\) points du plan, trois jamais alignés. Montrer qu'il existe une droite qui ne passe par aucun d'eux et en laisse exactement \(n\) de chaque côté.

Parcours suggéré

Un choix de problèmes de la shortlist, du plus accessible au plus difficile, où ce concept joue le premier rôle. La liste complète est plus bas.

Étape 1 — Premiers pas (1 ★)

  • 2013 C2 ★☆☆☆☆ · OIM P2 : Combien de droites faut-il pour séparer \(2013\) points rouges de \(2014\) points bleus, quelle que soit leur position ?
  • 2015 C2 ★☆☆☆☆ · OIM P1 : Des ensembles de points où toute paire a un point équidistant, mais où aucun point n'est centre de trois autres.
  • 2025 C1 ★☆☆☆☆ · OIM P1 : Couvrir un triangle de points entiers par \(n\) droites : combien d'entre elles peuvent ne pas suivre les trois directions du réseau ?

Étape 2 — Consolidation (2 ★)

  • 2006 C2 ★★☆☆☆ · OIM P2 : Une triangulation d'un \(2006\)-gone régulier : combien de triangles isocèles à deux côtés impairs au maximum ?
  • 2008 C1 ★★☆☆☆ : Combien de rectangles peut-on placer pour que deux d'entre eux se rencontrent exactement quand ils ne sont pas voisins sur un cercle ?
  • 2019 C4 ★★☆☆☆ : Un labyrinthe de droites peintes, des portes aux intersections : combien de chevaliers isolés Morgane peut-elle placer ?

Étape 3 — Approfondissement (3 ★)

  • 2008 G5 ★★★☆☆ : \(n\) droites en position générale et un point \(O\) : au moins \((k+1)(k+2)/2\) points d'intersection sont vus en traversant au plus \(k\) droites.
  • 2019 C6 ★★★☆☆ : Ordonner \(2n\) points pour que les angles du polygone obtenu se répartissent en deux groupes de même somme.

Étape 4 — Défi (4 ★ – 5 ★)

  • 2007 G6 ★★★★☆ : Un quadrilatère inscrit dans un autre : comparer son aire aux deux plus petits triangles des coins.
  • 2016 C7 ★★★★☆ · OIM P6 : Des escargots avancent ensemble le long de segments sécants : peut-on éviter toute rencontre ? Oui pour \(n\) impair, non pour \(n\) pair.

Géométrie combinatoire dans la shortlist

  • 2019 C6 : une droite sépare les points en deux groupes de \(n\), et l'on numérote en alternant les deux côtés.
  • 2016 C5 : des diagonales qui ne se coupent pas découpent un polygone à \(n\) côtés en au plus \(n - 2\) triangles.
  • 2018 G3 : un argument d'aire ; des triangles sans point intérieur commun ont une aire totale au plus \(\pi\).
  • 2019 C4 : \(n\) droites en position générale découpent le plan en \(\binom{n+1}{2} + 1\) régions.
  • 2022 C9 : la fonction cherchée compte des points du réseau sous une droite de pente irrationnelle.

Pour approfondir : Objectif Olympiades de Mathématiques, tome 4 (M. Aassila), p. 299 à 303 (dénombrer des points et des droites), p. 304 à 308 (formule d'Euler, dénombrer des régions et des figures), p. 309 à 315 (principe des tiroirs et géométrie), p. 316 (théorème de Helly : si des convexes du plan, en nombre fini, se coupent trois à trois, ils ont tous un point commun), p. 321 (théorème de Krasnosel'skii), puis les exercices jusqu'à p. 340.

Problèmes de la shortlist

28 problèmes · difficulté moyenne : ★★★★★ (3,3) · dont 9 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 3 · 2 ★ : 5 · 3 ★ : 6 · 4 ★ : 8 · 5 ★ : 6

Problème Difficulté Concepts
2025 C1 · OIM P1 ★☆☆☆☆ Principe des tiroirs · Récurrence et constructions récursives
2015 C2 · OIM P1 ★☆☆☆☆ Double comptage · Principe des tiroirs · Graphes : degrés, chemins, arbres
2013 C2 · OIM P2 ★☆☆☆☆ Récurrence et constructions récursives
2021 G3 ★★☆☆☆ AM-GM et moyennes
2019 C4 ★★☆☆☆ Graphes : degrés, chemins, arbres · Invariants et monovariants · Récurrence et constructions récursives
2018 G3 ★★☆☆☆ Récurrence et constructions récursives
2008 C1 ★★☆☆☆ Principe extrémal
2006 C2 · OIM P2 ★★☆☆☆ Récurrence et constructions récursives
2019 C6 ★★★☆☆ Invariants et monovariants · Récurrence et constructions récursives
2016 C5 ★★★☆☆ Principe extrémal · Récurrence et constructions récursives
2014 C5 · OIM P6 ★★★☆☆ Principe extrémal · Double comptage
2011 C3 · OIM P2 ★★★☆☆ Invariants et monovariants
2008 G5 ★★★☆☆ Récurrence et constructions récursives
2006 C3 ★★★☆☆ Bijections et dénombrement
2025 C7 ★★★★☆ Double comptage
2021 G6 ★★★★☆ Principe extrémal
2017 G6 ★★★★☆ Homothétie
2016 C7 · OIM P6 ★★★★☆ -
2014 C7 ★★★★☆ Invariants et monovariants
2009 G5 ★★★★☆ Principe extrémal · AM-GM et moyennes
2007 G6 ★★★★☆ Triangles semblables et similitudes
2007 C8 ★★★★☆ Double comptage
2022 C9 ★★★★★ Bijections et dénombrement · Partie entière et majorations
2020 G9 · OIM P6 ★★★★★ Principe extrémal
2017 C8 ★★★★★ Invariants et monovariants
2015 G8 ★★★★★ Principe extrémal
2006 C7 ★★★★★ Graphes : degrés, chemins, arbres
2006 G10 · OIM P6 ★★★★★ Coordonnées et nombres complexes