Un mariage magique

24 septembre 2016  - Ecrit par  Sylvain Barré Voir les commentaires (3)

Il y a en théorie des graphes un théorème qu’on nomme très joliment
« lemme des mariages ». Un vrai lemme, utile partout, pour tout faire. Il
survient ici où là, c’est un peu la clé à molette qui rend service dans
tout plein de situations. Souvent il a été question de ce lemme sur ce site. Parcourez l’article de Frédéric Le Roux Le lemme des Mariages qui en fait une très belle introduction.

Je viens ici vous présenter un tour de magie purement mathématique, en ce sens qu’il ne nécessite qu’une maîtrise abstraite du tour, la dextérité manuelle pour l’entourloupe n’est pas utilisée. Par contre, on peut faire usage de la parole pour faire monter le suspens et tenir en haleine ses spectateurs.

Ce qui est encore plus beau ici, c’est que le tour se présente à deux complices. Appelons-les Arthur et Baptiste. Le public se nommera Carole.

Arthur présente à Carole un jeu de 8 cartes. Il lui donne le paquet et lui demande de choisir trois cartes. Arthur regarde les trois cartes choisies par Carole et lui annonce être capable de faire deviner l’une d’elles à son complice Baptiste, uniquement en lui indiquant les deux autres. Comment est-ce possible ?


Imaginez un graphe dont les deux types de sommets soient : d’une part, le type A, les sous-ensembles de 3 cartes pris dans un paquet de huit et d’autre part, le type B : les couples de cartes (de ce paquet de huit).

Il y a une arête entre deux sommets de types différents si le couple est formé de cartes de l’ensemble à trois éléments.

Arthur a dans les mains un sommet de type A et communique à Baptiste un sommet de type B qui lui est relié. Voyez-vous arriver le lemme des mariages ?

Chaque sommet A est relié à 6 couples B et chaque sommet B est relié à 6 sommets A (pour compléter en un ensemble à trois éléments, il faut choisir une carte parmi les 6=(8-2) restantes). Nous sommes dans la situation homogène où la condition du lemme des mariages est toujours satisfaite : la valence en les sommets de type A est plus grande que celle des sommets de type B (ici égale).

Arthur doit faire un choix parmi six et par ce choix orienter celui de Baptiste, qui lui aussi aura un choix à faire parmi 6. Ce problème a-t-il une solution ?


Oui ! Le lemme des mariages nous dit qu’il existe une façon pour ces deux complices Arthur et Baptiste de se mettre d’accord pour réussir leur tour de magie, mais en pratique, quelques moyens qui soulagent la mémoire peuvent être les bienvenus. En voici un dans un cas plus confortable où il n’y aurait que 6 cartes. Ce sera l’occasion de décrire un peu plus en détail ce tour que je trouve magnifique.

Nommons les cartes Autruche, Baleine, Cheval, Dauphin, Éléphant et Fennec.
Les deux complices s’entendent pour convenir d’une résolution du problème des mariages comme cela. Partageons les 6 cartes en deux paquets de trois, orientés cycliquement (ABC) et (DEF), vous avez compris le raccourci des noms de cartes.

Parmi les trois cartes dans les mains d’Arthur, deux au moins sont dans un même 3-cycle. Alors Il s’agit de faire deviner la suivante dans l’ordre cyclique de la première carte annoncée dans le couple. La seconde carte (annoncée ou pas d’ailleurs, mais écartée au moins) est celle qui reste (qui se trouve dans l’autre cycle ou dans le même, mais alors qui précède la première).

Par exemple, si Arthur a en main ADF, il annoncera (F,A) et Baptiste devinera que la carte mystère est D, la suivante de F dans le cycle (DEF). Il n’a même pas besoin de connaître la seconde carte du couple (cela parce que nous n’avons pris que 6 cartes au total, pas 8).
Si Arthur avait en main ABC, il annoncerait (A,C) par exemple, mais il aurait aussi pu dire (B,A). Attention, avec 8 cartes, il ne peut plus y avoir ce type de liberté, c’est pour cela qu’il est beaucoup plus délicat de se mettre d’accord sur une résolution explicite du problème des mariages.
Attention, le tour ne peut plus marcher avec 9 cartes (pour seulement 3 cartes choisies).

En effet, la condition nécessaire du lemme des mariages n’est plus satisfaite,

Dans un paquet de $n$ cartes, Carole en choisit $k$. Arthur en révèle $k-1$ à Baptiste. Alors la valence des sommets de type $B$ est $n-k+1$ alors que celle des sommets de type $A$ est $ k!$. Si la condition $ k!\geq n-k+1$ est satisfaite alors la condition du lemme des mariages est aussi satisfaite. Qu’en est-il de la réciproque ? Il suffit de considérer l’ensemble de tous les sommets $A$, qui a des connexions avec tous les sommets de $B$. Ces ensembles ont pour cardinal, respectivement $n (n-1)...(n-k+1) / k! $ et $n (n-1)...(n-k+2) $. La comparaison de ces deux cardinaux redonne la même inégalité ! La condition $ k!\geq n-k+1$ était donc nécessaire. Ce qui conforte l’intuition : Arthur doit avoir plus de liberté de choix que Baptiste. Les experts font ce tour de magie avec un jeu de $n=52$ cartes pour $k=5$ cartes choisies par Carole ($5!=120 \geq 48$).


Pour finir, je vous mets au défi de trouver une méthode facile à mettre en œuvre avec votre complice préférée, pour 7 ou 8 cartes. J’attends vos propositions ! Je vous livrerai une solution pour 7 cartes la semaine prochaine (si besoin), le Gorille rejoignant le Fennec. Enfin, je remercie les étudiants Arthur, Baptiste et Carole de l’Université de Bretagne-Sud qui se sont pris au jeu.

Partager cet article

Pour citer cet article :

Sylvain Barré — «Un mariage magique» — Images des Mathématiques, CNRS, 2016

Commentaire sur l'article

  • Un mariage magique à la MMI

    le 26 septembre à 11:10, par Emmanuel Jacob

    Bonjour,

    Pour ceux qui voudraient voir ce tour de magie en œuvre (dans une variante élaborée, garantie des plus magnifiques et bluffantes !), je signale la prochaine exposition Magimatique de la Maison des Mathématiques et de l’Informatique, à Lyon, dès le 1er octobre, et jusqu’au 28 juin 2017. N’hésitez pas !

    Répondre à ce message
  • Proposition pour 8 cartes

    le 26 septembre à 12:46, par Emmanuel Jacob

    Ce lemme des mariages est beau mais pas très constructif... en particulier pour 2 complices qui cherchent un codage/décodage facile à mettre en place ! Voici ma proposition pour 8 cartes... qui n’est pas si simple. Je suis curieux de voir s’il y a plus élégant !

    Je désigne les 8 cartes par : $R_1$, $R_2$, $R_3$, $R_4$, $D_1$, $D_2$, $D_3$, $D_4$ (pour roi de pique, cœur, trèfle, carreau, dame de pique, cœur, trèfle, carreau).

    Il est plus facile de décrire d’abord comment Baptiste peut trouver la carte mystère (le décodage).

    Le décodage

    Si la 1ère carte indiquée par Arthur est la carte $R_i$, alors Baptiste sait que la carte codée est l’une des 3 cartes $\{R_{i+1}, R_{i+2}, D_i\}$ (on utilise l’ordre cyclique, ainsi $R_5=R_1$ par exemple, et $R_{i+1}, R_{i+2}$ et $D_i$ désignent bien des cartes de notre ensemble de 8 cartes). Plus précisément :

    $\bullet$ Si Arthur lui a indiqué $(R_i, R_{i+1})$ ou $(R_i, D_{i+1})$, alors Baptiste répond $R_{i+2}$.
    $\bullet$ Si Arthur lui a indiqué $(R_i, R_j)$ avec j différent de $i+1$, alors Baptiste répond $D_i$.
    $\bullet$ Si Arthur lui a indiqué $(R_i, D_j)$ avec j différent de $i+1$, alors Baptiste répond $R_{i+1}$

    Enfin, si la première carte est une dame, on inverse simplement le rôle des rois et des dames.

    Maintenant, voici comment Arthur peut coder la carte mystère. Ce codage est un petit peu plus compliqué à décrire, mais correspond exactement à la procédure de décodage : pour chaque choix de 3 cartes, Arthur n’a qu’une seule manière de choisir son couple de 2 cartes tel que l’algorithme de décodage donne effectivement la 3e carte....

    Le codage

    Si les 3 cartes sont 3 rois ou bien 2 rois et une dame, alors Arthur indiquera un roi en première carte. Nous nous plaçons maintenant dans ce cas pour fixer les idées (sinon, on inverse le rôle des rois et des dames).
    $\bullet$ Si les 3 cartes sont 3 rois, il y en a forcément 3 qui se suivent dans l’ordre cyclique. Pour l’ensemble $\{R_i, R_{i+1}, R_{i+2}\}$, Arthur choisit alors $(R_i, R_{i+1})$.
    $\bullet$ Dans les autres cas, il y a une dame $D_i$ et deux rois. On considère les sous-cas suivants :
    1. $\{D_i, R_{i}, R_{i-1}\}$ ou $\{D_i, R_{i}, R_{i+2}\}$. Arthur choisit $(R_i, R_{i-1})$ ou $(R_i, R_{i+2})$, respectivement.
    2. $\{D_i, R_{i-1}, R_{i+1}\}$. Alors Arthur choisit $(R_{i-1}, D_i)$.
    3. $\{D_i, R_j, R_{j+1}\}$ avec $j\neq i-1$. Alors Arthur choisit $(R_j, D_i)$.

    Répondre à ce message
    • Proposition pour 8 cartes

      le 27 septembre à 18:32, par Sylvain Barré

      Je ne connais pas de réponse « simple » à ce problème à 8 cartes. Par contre pour 7 cartes, en les ordonnant cycliquement, il y a une méthode très pratique...

      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