Polygones convexes : le problème de la fin heureuse

Piste rouge Le 28 novembre 2014  - Ecrit par  Pierre-Alain Cherix, Shaula Fiorelli Vilmart, Pierre de la Harpe Voir les commentaires (3)

D’abord une observation élémentaire, puis une question plus générale, un résultat partiel, une conjecture, des pratiquants résolus de l’idée fixe, et une postérité multiforme : ce sont souvent les ingrédients d’un beau sujet mathématique.
En guise d’illustration, voici une présentation du problème de la fin heureuse, plus connu en français (et sans doute en hongrois) sous le nom du happy end problem.

Les couleurs de cet article sont le rouge pour l’essentiel avec un peu de bleu au début et du noir vers la fin. La plupart des références sont hors piste.

Trois protagonistes, Esther Klein, Paul Erdös et George Szekeres apparaissent dans le happy end problem, les voici sur la photo en logo, en Australie, plus précisément à Newcastle, en 1984.

L’observation d’Esther Klein

Commençons par un élégant énoncé
dû à une jeune mathématicienne hongroise du début des années 30, Esther Klein :

Parmi cinq points du plan en position générale,
il en existe quatre qui sont les sommets d’un quadrilatère convexe.

Avant de justifier cet énoncé, rappelons quelques notions de géométrie plane.
Un ensemble de points du plan est en position générale
lorsque trois d’entre eux ne sont jamais alignés.
Une région du plan est convexe si,
chaque fois qu’elle contient deux points distincts, elle contient aussi le segment qui les joint.
Par exemple, les trois régions que voici

JPEG - 35.3 ko
Trois régions convexes

sont convexes, et les trois que voilà

JPEG - 39.2 ko
Trois régions non convexes
On observe que le segment reliant les deux points bleus de la région de gauche n’est pas contenu dans la région.

ne le sont pas.
Rappelons aussi que toute partie du plan est contenue dans des régions convexes,
et en particulier dans une région convexe bien particulière qui est la plus petite d’entre elles,
et qu’on appelle son enveloppe convexe.
Par exemple, la partie du plan formée des points rouges de la figure suivante
est contenue dans son enveloppe convexe qui est le polygone à bord bleu.

JPEG - 32.8 ko