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 :
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¶
- On choisit \(5\) points du réseau. Montrer que deux d'entre eux ont un milieu à coordonnées entières.
- Combien de points du réseau le segment de \((0, 0)\) à \((12, 18)\) contient-il ?
- 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}\).
- 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.
- 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é.
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 · Principe extrémal |
| 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 · Double comptage |
| 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 |