Le lemme des Mariages

Piste rouge Le 20 mars 2011  - Ecrit par  Frédéric Le Roux Voir les commentaires (2)

Le lemme des Mariages est un énoncé de théorie des ensembles qui peut se décrire en imaginant une société dans laquelle tous les mariages sont décidés de façon centralisée. Une application inattendue du lemme des Mariages à un problème d’approximation numérique s’avère pertinente pour l’étude des propriétés statistiques de certains systèmes dynamiques.

L’ordinateur central possède toutes les clés, de tous les vivants de Gondawa, et aussi des morts qui ont fait les vivants. Celles que nous portons ne sont que des copies. Chaque jour, l’ordinateur compare entre elles les clés de sept ans. Il sait ce que je suis, et aussi ce que je serai. Il trouve parmi les garçons ceux qui sont et qui seront ce qu’il me faut, ce qui me manque, ce dont j’ai besoin et ce que je désire. Et parmi ces garçons il trouve celui pour qui je suis et je serai ce qu’il lui faut, ce qui lui manque, ce dont il a besoin et ce qu’il désire. Alors, il nous désigne l’un à l’autre.

PNG - 35.7 ko

Le garçon et moi, moi et le garçon nous sommes comme un caillou qui avait été cassé en deux et dispersé parmi tous les cailloux cassés du monde. L’ordinateur a retrouvé les deux moitiés et les rassemble.

— C’est rationnel, dit Leonava.

René Barjavel, «La Nuit des Temps»

Le lemme des Mariages

A la suite de René Barjavel, imaginons une société dans laquelle tous les mariages sont décidés de façon centralisée. Tous les ans, on organise une Journée du Mariage. Chaque fille en âge de se marier fournit à l’Ordinateur Central la liste des garçons qui lui conviennent — avec l’accord de ceux-ci, évidemment. Sur la base de ces listes, l’ordinateur effectue le Mariage, c’est-à-dire qu’il associe à chaque fille le nom de l’un des garçons de sa liste. Comme la nôtre, cette société est strictement monogame : chaque fille est mariée à un seul garçon, chaque garçon à une seule fille. Et personne ne doit rester célibataire.


Une société avec six garçons et six filles. Odete a désigné Bertrand et Pamphile, Marinete a choisi Gontrand et Pamphile, etc..
Saurez-vous réaliser le Mariage ?...


L’ordinateur de Barjavel semble avoir la partie facile : il lui suffit de rassembler les deux moitiés du caillou... Mais dans notre société imaginaire, le Mariage n’est pas toujours possible. Pour pouvoir marier tout le monde, il doit évidemment y avoir autant de filles que de garçons. Comme ce n’est pas un point très important pour notre histoire, nous allons simplement supposer que c’est le cas. Mais ce n’est pas tout. Si deux filles ont choisi le même garçon, et aucun autre, l’ordinateur ne va pas pouvoir les marier simultanément. Et si ce problème n’arrive pas avec deux filles, il peut encore arriver lorsqu’on confronte les choix de trois filles : elles peuvent avoir toutes les trois choisi les deux mêmes garçons. Plus généralement, l’ordinateur échoue dès qu’il existe un groupe d’un certain nombre de filles dont les listes réunies contiennent un nombre inférieur de garçons.

On a donc trouvé une condition nécessaire pour que l’ordinateur puisse établir un Mariage.

Condition de Mariage : la réunion des listes d’un groupe quelconque de filles contient au moins autant de noms de garçons différents qu’il y a de filles dans le groupe.

Le lemme des Mariages, formulé en 1935 par le mathématicien Philip Hall,
est un énoncé mathématique qui dit que cette condition, dont on vient de voir qu’elle était nécessaire, est aussi suffisante :

Lemme des mariages Si la condition de Mariage est satisfaite, alors il est possible de marier toutes les filles, chacune à l’un des garçons de sa liste.

Démonstration

Le vocabulaire du mariage est un langage bien commode pour discuter de cet énoncé, et nous allons filer la métaphore pour aborder la démonstration.
Je vous propose donc de considérer une société constituée de filles et de garçons en âge de se marier. Chaque fille a établi une liste de garçons, et on suppose vérifiée la condition de Mariage :

La réunion des listes d’un groupe quelconque de filles contient au moins autant de noms de garçons différents qu’il y a de filles dans le groupe.

Il s’agit maintenant de montrer qu’il est possible de marier toutes les filles, en respectant les vœux de chacune.

Une fille, deux filles

Pour commencer doucement, essayons de marier un petit groupe de filles, sans se soucier des autres. Lorsqu’on l’applique aux “groupes” d’une seule fille, la condition de Mariage nous dit que la liste de chaque fille comporte au moins un nom.
Autrement dit, si on ne se préoccupe que d’une seule fille, on peut toujours la marier. Essayons avec un groupe de deux filles. On vient de voir que chacune avait mis au moins un nom sur sa liste ; pour qu’on ne puisse pas les marier toutes les deux simultanément, il faudrait que leurs listes ne comportent qu’un seul nom, et que ce soit le même ; mais ceci contredirait la condition de Mariage, puisque la réunion de leur deux listes doit comporter au moins deux noms distincts. On peut donc toujours marier deux filles quelconques (encore une fois, pour le moment, sans se soucier des autres).

Pour essayer de marier un groupe de trois filles, on pourrait commencer par marier deux d’entre elles sans se soucier de la troisième : on vient de voir que c’était possible. Puisque les listes des trois filles réunies ne comportent pas moins de trois noms distincts, on peut avoir l’impression qu’il est possible de marier la dernière à un troisième garçon. Cependant, la figure suivante montre que c’est parfois impossible. Cette remarque est importante, parce qu’elle disqualifie la stratégie la plus simple, qui serait d’essayer de marier les filles les unes après les autres, en ne se préoccupant que d’une seule à la fois.

Odete voudrait se marier avec Bertrand ou Pamphile ; Marinete a choisi Gontrand et Pamphile ; Rosinete n’accepterait que Bertrand. La condition de Mariage est vérifiée. Mais si on marie Odete à Bertrand et Marinete à Gontrand, c’est fichu pour Rosinete !


Trois filles

Essayons de marier un groupe de 3 filles.
Le raisonnement va être plus délicat. Nous distinguerons deux cas. Le premier, que nous appellerons le cas facile, est celui où les filles ont choisi beaucoup de garçons, plus que ce qui est réclamé par la condition de Mariage. Le deuxième cas, qualifié de difficile, est simplement le cas contraire ;
paradoxalement, dans le cas difficile, l’existence d’un groupe de filles dont les listes réunies contiennent juste assez de noms de garçons distincts sera la clé du Mariage.
 [1]

Précisons tout ceci. Pour le cas facile, nous supposons vérifiée une condition de Mariage renforcée :

  • la liste de chaque fille contient au moins deux noms distincts ;
  • la réunion des listes de deux filles quelconques contient au moins trois noms distincts.

Marions alors n’importe laquelle des trois filles à l’un des garçons de sa liste ; pour fixer les idées, nous l’appellerons Anatole. On examine maintenant les listes des deux filles restantes, et on raye le nom d’Anatole s’il y apparaît. Grâce à la condition renforcée, les listes amputées du nom d’Anatole comportent encore chacune au moins un nom, et leur réunion en contient au moins deux distincts. Nous sommes ramenés au cas de deux filles à marier vérifiant la condition de Mariage, et nous savons que nous pouvons encore marier ces deux filles conformément à leurs vœux. Le Mariage est fini... dans le cas facile seulement !

Comment faire dans le cas difficile, c’est-à-dire lorsque la condition de Mariage est satisfaite, mais pas la condition renforcée ? Si la condition renforcée n’est pas satisfaite, c’est que

  • la liste de l’une des filles contient exactement un nom,
  • ou la réunion des listes de deux des filles contient exactement deux noms distincts.

Supposons par exemple qu’on est dans le deuxième cas : la réunion des listes de deux des filles contient exactement deux noms distincts [2], disons Anatole et Basile. Nous marions ces deux filles avec ces deux garçons. Il reste à marier la troisième fille. D’après la condition de mariage, les trois listes réunies contiennent au moins trois noms distincts ; mais nous savons d’autre part que les listes réunies des deux premières ne contiennent pas d’autre noms que ceux d’Anatole et de Basile. Le troisième nom, disons Charles, vient donc nécessairement de la liste de la troisième fille : nous pouvons la marier à Charles. Ceci achève le Mariage dans le cas difficile.

Nous savons maintenant marier un groupe de trois filles. Le lecteur a probablement remarqué qu’à plusieurs endroits du raisonnement, nous nous sommes ramenés au cas d’un groupe de deux filles dont les listes vérifient la condition de Mariage. On peut résoudre le cas d’un groupe de quatre filles de façon tout à fait analogue, en utilisant le cas des groupes de deux ou trois filles que nous venons d’expliquer. On peut ensuite passer du cas de quatre filles au cas de cinq filles, et ainsi de suite. En pratique, pour ne pas avoir à rédiger une infinité de raisonnements,
on démontre ceci (simultanément pour toutes les valeurs possibles du nombre $n$) :

Si l’on peut marier tout groupe de $n$ filles ou moins vérifiant la condition de Mariage, alors on peut marier tout groupe de $n+1$ filles vérifiant la condition de Mariage.

On en déduit que le résultat est vrai pour un groupe de filles en nombre quelconque : puisqu’il est vrai pour $n=3$ filles ou moins il est vrai pour $n=3+1=4$, donc pour $n=4+1=5$, et ainsi de suite. Ce type de raisonnement s’appelle un raisonnement par récurrence.
On trouvera la démonstration générale permettant de passer de $n$ à $n+1$ dans les blocs dépliants ci-dessous.

Démonstration, version matrimoniale

On suppose que l’on a un procédé permettant de marier tout groupe de $n$ filles ou moins vérifiant la condition de Mariage ; cette hypothèse est appelé « hypothèse de récurrence ». On considère un ensemble de $n+1$ filles vérifiant la condition de Mariage, et on cherche à les marier simultanément. On va envisager deux cas disjoints.

Premier cas.
Le premier cas est celui où notre ensemble de filles vérifie la propriété suivante :

Pour tout sous-ensemble de filles [3], en nombre $p$, la réunion des listes de ces filles contient au moins $p+1$ noms de garçons différents.

On peut alors marier simultanément les $n+1$ filles de la façon suivante. On choisit n’importe quelle fille de l’ensemble, et on la marie à n’importe quel garçon de sa liste.
On efface maintenant le nom du marié de toutes les listes où il apparaissait. Considérons l’ensemble des $n$ filles restantes, munies de leurs listes modifiées.
Pour tout sous-ensemble de $p$ filles parmi celles qui restent, la réunion des listes de ces $p$ filles contient au moins $p$ noms de garçons
(elle en contenait au moins $p+1$ avant panachage, et on a enlevé le nom d’un unique garçon). Autrement dit, la condition de Mariage est encore vérifiée.
D’après l’hypothèse de récurrence, on peut marier les $n$ filles restantes. Le Mariage est fini dans ce cas.

Second cas. On peut maintenant supposer qu’on n’est pas dans le premier cas, ce qui signifie exactement ceci :

Il existe un sous-ensemble de filles dont la réunion des listes contient exactement autant de noms de garçons différents qu’il y a de filles.

L’hypothèse de récurrence nous permet de marier ce groupe de filles avec le groupe des garçons désignés par leurs listes, du moment que l’on ne se soucie pas des autres.
Le point délicat consiste à vérifier qu’il est encore possible de marier l’ensemble des filles restantes parmi l’ensemble des garçons restants.

Pour bien comprendre ce point délicat, on peut imaginer que toutes les filles à marier, depuis le début, sont réunies en un même lieu. Le groupe des $p$ filles que nous venons de marier est rassemblé.
Dans le groupe restant, on isole un sous-ensemble de filles, disons qu’il y en a $q$. Et pour y voir plus clair, on demande (gentiment) aux autres de quitter provisoirement la scène.
Il reste devant nous $p$ filles déjà mariées et $q$ filles qui ne le sont pas encore. L’une après l’autre, on demande à ces $p+q$ filles de venir écrire leur liste sur un grand tableau, en omettant les noms qui y ont déjà été inscrit par une autre fille. On obtient ainsi la liste réunie, et on sait, d’après la condition de Mariage, qu’elle ne contient pas moins de $p+q$ noms. On efface ensuite le nom des $p$ garçons qui ont été mariés aux $p$ filles : il reste alors une liste d’au moins $q$ noms. Le point clé est que tous les noms restants ont été inscrits par l’une des $q$ filles non mariées. En effet, aucun des noms restants n’était sur la liste de l’une des filles déjà mariée, puisque la liste réunie de ces $p$ filles contenait exactement les $p$ noms de ceux qui sont devenus leur maris.

Sur les listes des filles restant à marier, on efface les noms des garçons déjà mariés. La discussion du paragraphe précédent revenait à vérifier que le groupe des filles restantes, munies de leurs listes modifiées, satisfait à nouveau la condition de Mariage : la réunion des listes modifiées de tout groupe de $q$ filles restantes contient au moins $q$ noms. On invoque une dernière fois l’hypothèse de récurrence pour marier les filles restantes. Et c’est fini !

Enoncé et démonstration, version « théorie des ensembles »

Donnons d’abord l’énoncé complet, dans la langue de la théorie des ensembles.

Lemme des mariages Considérons deux ensembles finis $F,G$, et une application $c$ de $F$ dans l’ensemble des parties de $G$. Pour toute partie $F_0$ de $F$, on note $c(F_0)$ la réunion des ensembles $c(f)$ lorsque $f$ parcourt $F_0$. Supposons que l’hypothèse suivante est réalisée :

pour chaque partie $F_0$ de $F$, l’ensemble $c(F_0)$ contient au moins autant d’éléments que $F_0$.

Alors il existe une application $m$ de $F$ dans $G$, injective [4]
et telle que, pour tout $f$ dans $F$, $m(f)$ appartient à $c(f)$.

Démonstration
On raisonne par récurrence sur le nombre d’éléments de $F$. Le résultat est facile lorsqu’il n’y a qu’un seul élément. Soit $n$ un entier supérieur ou égal à $1$.
Supposons que le lemme est vrai pour tout ensemble $F$ ayant $n$ éléments ou moins. On considère un ensemble $F$ de $n+1$ éléments, et $G$ et $c$ vérifiant l’hypothèse de l’énoncé.

Premier cas.
On étudie d’abord le cas où pour toute partie $F_0$ de $F$ qui n’est ni vide ni égale à $F$, l’ensemble $c(F_0)$ contient au moins un élément de plus que $F_0$.

On construit alors $m$ de la façon suivante. Soit $f_0$ n’importe quel élément de $F$, et $g_0$ un élément de $c(f_0)$. On note
$F'$ l’ensemble $F$ privé de $f_0$,
$G'$ l’ensemble $G$ privé de $g_0$,
et, pour chaque élément $f$ de $F'$, on définit l’ensemble $c'(f)$, qui vaut $c(f)$ privé de $g_0$.
On vérifie que $F'$, $G'$ et $c'$ satisfont les hypothèses du lemme des mariages. Par hypothèse de récurrence, il existe une application injective $m'$ de $F'$ dans $G'$
telle que, pour tout $f$ dans $F'$, $m'(f)$ appartient à $c(f)$ privé de $g_0$. On étend cette application en une application $m$ de $F$ dans $G$ en posant $m(f_0)=g_0$.
L’application $m$ vérifie les propriétés voulues.

Second cas.
Si l’hypothèse du premier cas n’est pas réalisée, c’est qu’il existe une partie non vide $F_0$ de $F$ telle que l’ensemble $G_0 = c(F_0)$ contient exactement le même nombre d’éléments que $F_0$. On note
$F'$ l’ensemble $F$ privé de $F_0$,
$G'$ l’ensemble $G$ privé de $G_0$,
et, pour chaque élément $f$ de $F'$, on définit l’ensemble $c'(f)$, qui vaut $c(f)$ privé de $G_0$.
Vérifions que $F'$, $G'$ et $c'$ satisfont l’hypothèse du lemme des Mariages.
Soit $F'_0$ une partie de $F'$. On considère la réunion des ensembles disjoints $F'_0$ et $F_0$. L’ensemble $c(F'_0 \cup F_0)$ est l’union des ensembles disjoints $c'(F'_0)$ et $G_0$ ; d’après l’hypothèse du lemme des mariages, il contient au moins autant d’éléments que $F'_0 \cup F_0$. D’autre part $F_0$ et $G_0 = c(F_0)$ ont exactement le même nombre d’éléments. On en déduit que $c(F'_0)$ a au moins autant d’éléments que $F'_0$ : la condition de Mariage est satisfaite.
On applique l’hypothèse de récurrence deux fois, la première fois à $F'$, $G'$ et $c'$, la seconde fois à $F_0$, $G_0$ et la restriction de $c$ à $F_0$. On définit ainsi, indépendamment sur $F$ et sur $F_0$, une application $m$ qui vérifie à nouveau les propriétés voulues.

Une application aux systèmes dynamiques

JPEG - 223.4 ko

À la fin des années 1960, l’astronome Michel Hénon étudiait numériquement, selon ses propres termes, des « applications quadratiques préservant les aires ». L’article publié en 1969 cite des motivations d’origines diverses, comme le problème restreint des trois corps en astronomie, le mouvement d’une étoile dans une galaxie asymétrique, ou encore la trajectoire de particules dans des accélérateurs [5]. Qu’y a-t-il de commun à toutes ces situations ? Il s’agit à chaque fois d’étudier un système qui évolue au cours du temps, et qui est suffisamment simple pour qu’on puisse, à l’aide de coordonnées, représenter chaque état du système par un point du plan. La physique fournit des lois d’évolution qui permettent, pour chaque état du système, de calculer l’état “suivant”, disons une seconde plus tard.
Puisque chaque état est assimilé à un point du plan, la loi d’évolution devient une transformation $T$ du plan, qui fait correspondre à chaque point le point suivant.
Cette transformation possède des propriétés mathématiques issues des propriétés physiques des systèmes étudiés. Comme les modèles considérés sont réversibles (on peut inverser les lois de la physique et remonter le temps), la transformation est inversible : il existe une autre transformation qui envoie chaque point sur le point précédent.
D’autre part, dans chacun de ces modèles, l’énergie du système est préservée, et ceci se traduit par une condition géométrique étonnante : la transformation $T$ préserve les aires. Ceci signifie que chaque petit carré se déforme en une nouvelle figure qui occupe la même surface que le petit carré initial. Ce qui ne l’empêche pas de pouvoir prendre des formes biscornues, comme sur cette animation.

Une famille de transformations préservant les aires. Chaque point $p$ se déplace jusqu’à son état suivant $T(p)$, qu’il atteint à la fin de l’animation. La grille se déforme sous l’effet de la transformation, mais l’aire des carrés déformés reste constante au cours du temps.


A vrai dire, Hénon ne s’intéressait pas directement aux systèmes physiques évoqués plus haut. À la place, il avait trouvé une application $T$ décrite par une formule très simple [6], et qui semblait présenter la même richesse de comportement que ces systèmes physiques. Etant donné un état initial du système représenté par un point $p$, les états successifs sont représentés par les images successives du point $p$ par la transformation $T$ ; la suite de ces états successifs s’appelle l’orbite du point $p$. L’allure de l’orbite traduit le comportement à longue échéance du système étudié. Hénon utilisait un ordinateur pour tracer des orbites de sa transformation, et obtenait des dessins comme celui-ci. [7]

JPEG - 92.4 ko
Quelques orbites de la transformation de Hénon

Quelques orbites de l’application de Hénon. La transformation $T$ envoie successivement $p$ sur $q$, $q$ sur $r$, $r$ sur $s$, et ainsi de suite. L’orbite de $p$ est la suite des points $(p,q,r,s,t,...)$.


Le mathématicien Peter Lax a reçu le prix Abel 2005 pour ses contributions à l’étude théorique et numérique des équations aux dérivées partielles. En entendant Hénon présenter ses travaux, Lax s’est fait la réflexion suivante. Comme tous les ordinateurs, celui utilisé par Hénon pour faire ses dessins calcule avec une précision importante mais limitée, et doit effectuer des approximations numériques. Supposons par exemple qu’on travaille avec 6 chiffres après la virgules, et que, pour calculer un point suivant pour la transformation $T$, on doive calculer le carré du nombre
\[ 0,123456. \]
Le résultat exact est
\[ 0,015241383936 \]
mais l’ordinateur, qui ne garde que 6 décimales, utilisera le résultat approché
\[ 0,015241. \]
Ainsi, la transformation réellement utilisée par l’ordinateur ne préserve les aires qu’approximativement, et elle n’est plus inversible : si deux points ont des états suivants trop proches, l’approximation va tronquer les décimales différentes et confondre les deux états suivants ; il ne sera alors plus possible de remonter au point initial. Peter Lax s’est alors demandé s’il était possible, au moins en théorie, d’utiliser une approximation numérique qui soit encore inversible.

Reprenons l’exemple de l’animation montrant une grille qui se déforme. Imaginons que chaque petit carré de la grille initiale représente un pixel (un point) de l’écran de l’ordinateur. Imaginons également que la précision avec laquelle calcule l’ordinateur soit exactement la taille d’un pixel (cette précision est en réalité très supérieure, mais ceci ne changera rien au raisonnement). L’approximation effectuée par l’ordinateur revient alors à remplacer chaque carré déformé, représentant l’image d’un pixel par la transformation $T$, par un petit carré de la grille initiale. Pour que l’approximation ne soit pas trop mauvaise, c’est-à-dire pour qu’elle ressemble suffisamment à la transformation $T$, on demande que le petit carré déformé rencontre le petit carré de la grille initiale qui va le remplacer.
D’autre part, pour que la transformation approchée obtenue soit inversible, on ne doit pas remplacer deux carrés déformés différents par le même petit carré.
La question de Lax s’exprime alors ainsi :

Peut-on choisir, pour chaque carré déformé, un petit carré de la grille initiale parmi ceux qui le rencontrent, de façon à ce que deux petits carrés déformés ne soit jamais associés au même petit carré ?

Imaginons maintenant que chaque petit carré déformé représente une fille, et que chaque petit carré initial représente un garçon. On superpose alors la grille déformée (représentant le groupe de filles) et la grille initiale (représentant le groupe des garçons). Imaginons encore que chaque carré-fille inscrit sur sa liste de mariage tous les carrés-garçons qu’elle rencontre sur le dessin. Par exemple, la liste du carré-fille colorié en rose comporte les quatre carrés-garçons coloriés en bleu.

Le problème de Lax revient alors à savoir si le Mariage est possible dans cette société de carrés. Avec le lemme des Mariages, la question devient : la condition de Mariage est-elle réalisée ? Autrement dit, la liste réunie de tout groupe de carrés-filles contient-elle au moins autant de carrés-garçons ?
Considérons un ensemble de carrés-filles. Leur liste réunie contient tous les carrés-garçons rencontrés par l’une d’entre elles. Ainsi, la réunion des carrés-filles est contenue dans la réunion des carrés-garçons de leur liste. Il est temps de se rappeler la propriété essentielle de notre transformation $T$ : elle préserve les aires. Chaque carré-fille occupe donc la même surface que chaque carré-garçon. Puisque la réunion des garçons de la liste contient la réunion des filles, il doit y avoir au moins autant de garçons que de filles : la condition de Mariage est remplie.
Ceci montre que le problème d’approximation de Lax admet une solution.

Conséquences du théorème de Lax

La remarque de Lax, et son raisonnement que nous venons de reproduire, sont très élégants [8]. Ce résultat a cependant peu d’intérêt en pratique : à ma connaissance, personne ne l’a utilisé pour améliorer les approximations numériques. Par contre, le résultat de Lax a des conséquences théoriques : il est à la base d’une théorie plus récente, due au mathématicien Steve Alpern, qui établit un lien entre les systèmes dynamiques topologiques et la théorie ergodique [9]. Je ne peux évidemment pas entrer dans les détails, mais j’essaie d’expliquer ceci brièvement.

Nous avons vu que la transformation $T$ de Hénon, et celle représentée sur l’animation, préservent les aires. Mais elles ont également une propriété de continuité : elles étirent les petits carrés sans les déchirer. Les transformations continues sont les objets d’étude des systèmes dynamiques topologiques.
Les ergodiciens, eux, considèrent des transformations qui préservent les aires, mais qui ne sont pas nécessairement continues : elles transforment chaque petit carré en une poussière de points — mais dont la réunion occupe la même surface que le carré initial.
Le théorème d’Alpern dit que les propriétés dynamiques statistiques typiques des transformations de la théorie ergodique sont également typiques des transformations continues préservant les aires. Le mot « typique », ici, permet de mettre de côté les cas trop particuliers, comme celui de la transformation qui ne bouge pas les points (que les mathématiciens appellent l’identité). Par exemple, une propriété dynamique statistique typique de ces systèmes est le « mélange faible », qui est une certaine forme de « chaos » [10].

Fin

Dans ce texte, j’ai essayé d’expliquer comment un énoncé mathématique élémentaire, le lemme des Mariages, en rencontrant dans le cerveau d’un mathématicien une question suscitée par des simulations sur ordinateur de phénomènes physiques, a donné naissance à des résultats théoriques difficiles. Le lemme des Mariages, qui permet de marier bien d’autres choses que des pixels, est régulièrement utilisé dans différents contextes mathématiques [11]. Je vous propose d’essayer à votre tour de jouer au Mariage, avec ce petit problème en forme de devinette emprunté à la page wikipedia sur le sujet.

Devinette
On distribue un jeu de 52 cartes en faisant treize paquets de quatre cartes chacun. Expliquer pourquoi il est possible d’ordonner les treize paquets de façon à ce que le premier contienne un as, le second un 2, et ainsi de suite jusqu’au treizième qui contient un Roi. Qui sont les filles ? Qui sont les garçons ? Pourquoi la condition de Mariage est-elle satisfaite ?

Post-scriptum :

L’auteur remercie les personnes suivantes pour leurs remarques constructives :
Muriel Altabef, François Brunault, Jérôme Buzzi, Eric Dumas, Vincent Guirardel, Claire Lacour.

Article édité par Jérôme Buzzi

Notes

[1L’explication qui suit n’est certainement pas la plus courte possible, mais elle a l’avantage de se généraliser à un nombre quelconque de filles.

[2Le premier cas se traite de façon analogue.

[3Ce sous-ensemble doit être un « vrai » sous-ensemble : il doit contenir au moins une fille, et ne pas les contenir toutes.

[4C’est-à-dire telle que $m(f)$ est différent de $m(f')$ lorsque $f$ est différent de $f'$.

[5Hénon, M.
Numerical study of quadratic area-preserving mappings.
Quart. Appl. Math. 27 (1969) 291-312.

[6Il s’agit en fait d’une famille de transformations, dont les formules se trouve au bas de cette page.

[7En réalité, les systèmes physiques évoqués par Hénon sont décrits initialement par trois coordonnées, et leur évolution est modélisée par des équations différentielles. On se ramène à l’itération d’une transformation du plan en utilisant une section de Poincaré (voir par exemple
ici). Le lien entre la conservation de l’énergie et la propriété de conservation des aires est expliqué ici.

[8Le théorème d’approximation uniforme qui en découle est publié dans
Lax, Peter D. Approximation of measure preserving transformations. Comm. Pure Appl. Math. 24 (1971) 133-135.

[9Voir par exemple Alpern, Steve ; Prasad, V. S. Properties generic for Lebesgue space automorphisms are generic for measure-preserving manifold homeomorphisms. Ergodic Theory Dynam. Systems 22 (2002), no. 6, 1587-1620.

[10La transformation de Hénon dont on a dessiné plus haut quelques orbites n’est pas typique : chaque orbite évolue le long d’une courbe, et ceci est une propriété très spéciale, qui interdit le mélange faible.

[11Deux exemples au hasard, pour spécialistes uniquement ! En analyse harmonique, voir l’appendice de H . Weyl, Almost periodic invariant vector sets in a metric vector space, American Journal of Mathematics, 71 (1949), 178-205 ; en probabilités, voir Chapitre 11 de R. Dudley, Real Analysis and Probability, Wadsworth, Pacific Grove, CA, 1989.

Partager cet article

Pour citer cet article :

Frédéric Le Roux — «Le lemme des Mariages» — Images des Mathématiques, CNRS, 2011

Commentaire sur l'article

  • Le lemme des Mariages

    le 21 mars 2011 à 15:29, par Maxime Bourrigan

    Merci, Frédéric, pour ce bel article.

    J’ai une question à propos du lemme des mariages, qui vient d’une interférence avec un truc de Dijkstra au sujet du principe des tiroirs que j’ai lu il y a peu : http://www.cs.utexas.edu/users/EWD/transcriptions/EWD09xx/EWD980.html

    Dans ce texte, Dijkstra dit en substance qu’une partie de l’émerveillement produit par une preuve utilisant le principe des tiroirs sous sa forme classique (Si on a plus de chaussettes que de tiroirs, un tiroir accueillera plusieurs chaussettes) vient du fait que la formulation, même si elle est très plaisante, nécessite un gros effort intellectuel pour être appliquée. Essentiellement, il faut pas mal de temps pour comprendre qui vont être les tiroirs et qui les chaussettes avant d’appliquer le principe. Dijkstra dit alors que le principe des tiroirs a une forme différente, qu’il appelle « purifiée », beaucoup moins « catchy » mais beaucoup plus efficace : dans une collection de nombres, le maximum est supérieur à la moyenne.

    Je me demandais si une chose similaire pouvait être faite avec le lemme des mariages : les remarques de Dijkstra semblent s’y appliquer tout aussi bien. La formulation est incisive, basée sur une métaphore forte, les preuves l’utilisant héritent souvent d’une patine d’élégance et l’appliquer demande un peu d’astuce, comme le suggère ta devinette. Penses-tu qu’il existe une version « purifiée » du lemme des mariages ? Cela semble d’autant plus crédible qu’il semble relié à un grand nombre de résultats en combinatoire, dans des contextes variés : théorème de König sur les graphes bipartis, de Dilworth sur les ensembles ordonnés, etc.

    Et encore bravo !

    Répondre à ce message
  • Le lemme des Mariages

    le 27 mars 2011 à 21:26, par Frédéric Le Roux

    Bonjour Maxime,

    merci pour ton commentaire. Je dois dire que je tiens beaucoup aux images en maths, et que je préfère penser à des tiroirs ou à des mariages qu’à des nombres. Je n’ai pas vraiment l’impression que j’aurais plus de facilité à appliquer la formulation de Dijkstra : ça dépend probablement du problème (et aussi de la forme d’esprit de celui qui s’y attaque). Le fait de penser à des carrés, ou à des cartes à jouer, comme à des filles ou des garçons, ça demande un gros effort d’abstraction ; mais je ne sais pas si l’effort est moindre si on essaie d’appliquer la formulation purement ensembliste du Lemme.

    Pour moi, l’émerveillement vient plutôt du fait que le même énoncé peut s’appliquer à des objets très différents, quelle que soit la formulation de cet énoncé.

    Frédéric

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM