Un mariage magique

El 24 septiembre 2016 - Escrito por Sylvain Barré Ver los comentarios (6)

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.

Comentario sobre el artículo

Un mariage magique à la MMI

le 26 de septiembre de 2016 à 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 de septiembre de 2016 à 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 de septiembre de 2016 à 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

Proposition pour 7 cartes

le 1ro de octubre de 2016 à 11:28, par Sylvain Barré

Les penser dans un ordre cyclique. Alors, les 3 cartes choisies par Carole sont 1) soit isolées, 2) soit deux d’entre-elles sont collées.
Dans le cas 1) il y a un espace de longueur 2 (dans le cycle) entre deux des cartes choisies et deux autres espaces de longueur 1. Disons que les cartes choisies sont CEG dans le cycle ABCDEFG. Alors, Arthur choisit (C,E) (espacées de 2 crans dans l’ordre positif) pour que Baptiste devine G, la lettre deux crans plus loin.

Dans le cas 2), deux des cartes choisies sont A et B. Alors la stratégie est que Baptiste devine toujours la suivante de la première carte, et ce parce que les deux cartes annoncées ne sont pas espacées de 2 dans l’ordre cyclique positif.
Plus explicitement : si la troisième est C (cas de trois cartes collées) Arthur annonce (B,A) (surtout pas (A,C) qui conduirait Baptiste dans le cas 1) !) Aussi, dans le cas ABCDEFG Arthur annonce (A,D), ainsi de suite pour les autres cas jusqu’au cas ABF où Arthur annonce (A,F), bien espacés de 2, mais dans le désordre, on reste bien dans le cas 2).
Répondre à ce message

Proposition pour 7 cartes

le 2 de octubre de 2016 à 14:55, par Emmanuel Jacob

Joli! Chercher codage et décodage invariants par translation cyclique simplifie grandement le problème! Ainsi, il n’y a plus que 5 tirages possibles de 3 cartes, et 6 «messages codés» possibles. Dans le codage que tu proposes, le message codé «AB» n’est ainsi jamais utilisé (et n’a donc pas de décodage associé).

Avec 8 cartes, on pourrait procéder de même... sans pour autant que l’on puisse trouver une procédure de codage/décodage aussi simple. Dans ma proposition pour 8 cartes, j’ai d’ailleurs aussi proposé codage et décodage présentant des symétries... mais pas celles de l’ordre cyclique. En fait j’ai travaillé avec $\mathbb Z/4\mathbb Z \times \mathbb Z/2\mathbb Z$ plutôt que $\mathbb Z/8\mathbb Z$ (cela me paraissait plus naturel pour un jeu de cartes, en particulier pour la photo de présentation du billet avec les rois et les dames...)
Répondre à ce message

Proposition pour 7 cartes

le 2 de octubre de 2016 à 15:16, par Sylvain Barré

La main donnée en photo ici brouille peut-être les idées, j’ai voulu mettre quatre mariages :-) Il y a peut-être d’autres valeurs de $n$ et $k$ qui se prêtent bien à codages-décodages confortables...
Répondre à ce message

Dejar un comentario

Foro sólo para inscritos

Para participar en este foro, debe registrarte previamente. Gracias por indicar a continuación el identificador personal que se le ha suministrado. Si no está inscrito/a, debe inscribirse.

Conexión | inscribirse | ¿contraseña olvidada?

El autor

Sylvain Barré

Maître de conférences, Université de Bretagne-Sud

Un mariage magique

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

Comentario sobre el artículo