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é.
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 |