Un mariage magique

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.