problème de la fin heureuse

Placez cinq points sur une feuille, sans en aligner trois. Parmi eux, il est toujours possible d'en choisir quatre qui dessinent un quadrilatère sans creux : aucun sommet ne rentre à l'intérieur du triangle formé par les trois autres.

Cette garantie est le problème de la fin heureuse. Son nom vient de l'histoire racontée par Paul Erdős : les travaux menés autour du problème ont rapproché Esther Klein et George Szekeres, mariés en 1937.

Le problème de la fin heureuse est le théorème d'Esther Klein, découvert et démontré en 1933. Il s'applique à cinq points distincts du plan en position générale, ce qui signifie qu'aucun groupe de trois points n'est aligné. Il affirme que quatre de ces points sont les sommets d'un quadrilatère convexe. Les quatre points peuvent donc être parcourus dans un ordre tel que le quadrilatère n'ait aucun angle rentrant.

Pour chaque entier n au moins égal à 3, la généralisation cherche le nombre minimal, noté N(n), de points en position générale qui garantit n points en position convexe. Le résultat d'Esther Klein est exactement le cas n = 4 : N(4) = 5. Cette question générale est connue sous le nom de conjecture d'Erdős-Szekeres ; Paul Erdős, George Szekeres et Andras Sárközy ont contribué à son étude.

Le théorème est aussi intimement lié au théorème d'Erdös-Szekeres sur les suites monotones. Cette relation relie une question de disposition de points à un principe combinatoire portant sur l'ordre.

Considérons les cinq points A(0 ; 0), B(4 ; 0), C(5 ; 3), D(2 ; 5) et E(2 ; 2). Pour trois points ordonnés P, Q et R, le nombre Δ(P,Q,R) mesure de quel côté se fait le virage de P vers Q puis R.

1. Pour les dix triplets, on obtient Δ(A,B,C) = 12, Δ(A,B,D) = 20, Δ(A,B,E) = 8, Δ(A,C,D) = 19, Δ(A,C,E) = 4, Δ(A,D,E) = −6, Δ(B,C,D) = 11, Δ(B,C,E) = 8, Δ(B,D,E) = 6 et Δ(C,D,E) = 9. Aucune valeur n'est nulle : les cinq points sont bien en position générale.

2. Parcourons A, B, C puis D. Les quatre virages successifs valent Δ(A,B,C) = 12, Δ(B,C,D) = 11, Δ(C,D,A) = 19 et Δ(D,A,B) = 20.

3. Ces quatre nombres sont strictement positifs. Les virages ont tous le même sens : A, B, C et D forment donc un quadrilatère convexe, tandis que E se trouve à l'intérieur.

Le contrôle est refaisable en reliant A–B–C–D–A : chaque côté appartient au contour extérieur et le point E reste enfermé. La figure rend visibles ces cinq données et les quatre sommets retenus.

Devant cinq points, commencez par contrôler qu'ils sont distincts et qu'aucun triplet n'est aligné. Si ces deux conditions sont satisfaites, le théorème garantit un choix de quatre sommets convexes sans demander de tester les cinq sous-ensembles un par un.

Pour une configuration dessinée, repérez son contour extérieur. S'il contient au moins quatre des cinq points, quatre points du contour fournissent le quadrilatère cherché. Si le dessin est ambigu, le signe des virages successifs donne un contrôle calculable.

Lorsque la question porte sur n sommets convexes plutôt que sur quatre, il faut passer à la formulation générale avec N(n). Le cas de cinq points ne suffit alors plus à répondre.

Le problème de la fin heureuse et un quadrilatère convexe. Le premier est une garantie portant sur tout ensemble admissible de cinq points ; le second est l'objet que quatre points choisis doivent former. Une figure peut donc montrer un quadrilatère convexe sans illustrer, à elle seule, la garantie universelle.

Le théorème d'Esther Klein et le théorème d'Erdös-Szekeres sur les suites monotones. Ils sont intimement liés, mais leurs données ne sont pas les mêmes : l'un part de points du plan, l'autre de suites ordonnées.

Trois points alignés. La position générale n'est plus satisfaite ; une valeur Δ nulle le signale. Il faut alors traiter directement cette configuration au lieu d'invoquer le théorème.

Seulement quatre points. La conclusion n'est pas garantie : un point peut se trouver à l'intérieur du triangle formé par les trois autres. Ce cas charnière explique la valeur minimale N(4) = 5.

Existence, non unicité. Le théorème promet au moins un sous-ensemble convenable ; il ne dit pas qu'un seul choix est possible. Pour compter tous les quadrilatères convexes d'une configuration, il faut examiner les différents sous-ensembles.

Changer la valeur de n. L'égalité N(4) = 5 ne donne pas N(n) pour tous les entiers n au moins égaux à 3. La question générale relève de la conjecture d'Erdős-Szekeres.

Quadrilatère convexe — Identifiez précisément l'objet géométrique dont le théorème garantit l'existence parmi cinq points.

Théorème d'Erdös-Szekeres — Prolongez la lecture vers le résultat sur les suites monotones auquel le problème est intimement lié.

La géométrie convexe — Replacez la recherche de sommets en position convexe dans son cadre géométrique plus large.