Forum de mathématiques - Bibm@th.net

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Lemme des mariages: une application simple

Bonjour,

En admettant ce résultat (*):
https://www.bibmath.net/dico/index.php? … iages.html

Montrer que si on répartit de façon quelconque un jeu de bridge (52 cartes ordinaires) en 13 paquets de 4 cartes, alors un des paquets contient un "as", un autre un "deux", ..., et enfin un dernier paquet un "Roi".

(*) On peut le prouver par récurrence, ou dans le cadre de la théorie des graphes avec les couplages, bref par divers procédés, mais ce n'est pas du tout le but ici: on demande juste de l'appliquer.

Bonne chance
Alain

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 903

Re : Lemme des mariages: une application simple

Le lien donné ne semblant pas concerner la rubrique directement, la voici en mode textuel ( en substance, mais sa formalisation est accessible sur ce site avec la loupe...):

Théorème : Soit Fet G deux ensembles finis, et soit  c une application de G dans P(F) , l'ensemble des parties de F.
On suppose que pour toute partie X de G, le nombre d'éléments de ⋃x∈X  c(x) est supérieur ou égal à celui de X.
Alors il existe une application injective M de G dans F telle que
M(g) est élément de c(g) pour tout g ∈ G.

Ce théorème s'appelle lemme des mariages en raison de l'interprétation suivante :
G désigne un ensemble (fini) de garçons,
F désigne un ensemble (fini) de filles, et c est l'application qui à chaque garçon associe l'ensemble des filles qui lui plaisent. Alors, si pour chaque sous-groupe de garçons, il y a plus de filles qui plait à au moins l'un d'entre eux que le nombre de garçons de ce sous-groupe, on peut marier chaque garçon à une fille différente qui lui plait. Bien sûr, on peut échanger le rôle des filles et des garçons!
Évidemment dans cet exemple social, les mots "fini" sont superflus, l'humanité comptant un nombre fini d'individus, mais bon, on est sur un forum de maths non?
Il ne l'est plus (quoique ?) à l'échelle du cosmos: martien aime martienne, vénusien aime vénusienne.... :-) et rien ne dit que la liste s'arrête...

Remarque: la réciproque étant claire, c'est cette implication-là qui constitue véritablement le lemme.
On peut s'imprégner un peu du truc en voyant par exemple que si deux gars ont le béguin pour une seule fille, mais la même, la conclusion fera chou blanc.

▼indication

Il suffit de procéder par analogie, afin de pouvoir se placer dans le cadre du lemme.
Ainsi quel est G, etc.
Ensuite comprendre pourquoi cela va marcher.

▼une solution

La preuve s'effectue rapidement en remarquant que la répartion des 52 cartes en 13 tas de 4 peut se modéliser ainsi (aux couleurs de cartes près, vu que la question ne concerne que les hauteurs des cartes):
G est l'ensemble des tas, F est l'ensemble { As  2, 3, ..., Roi},
et c est la fonction qui donne pour chaque tas la partie de F contenue dans ce tas ( toutes les hauteurs de cartes présentes dedans).
En considérant n tas quelconques  , soit m le nombre d'éléments de F globalement présents dans ces n tas.
On a donc 4n cartes de m hauteurs, et comme il n'y a que 4 couleurs, on a forcément 4n au plus égal à 4m, donc n est inférieur ou égal à m.
Il existe donc une injection M de G dans F telle que M(g) soit dans le tas g (ie M(g) dans c(g) ), pour tout g , selon le lemme des mariages.

Remarque: la dualité du paquet 13 cartes ( main) x 4 joueurs versus 4 couleurs x 13 cartes impacte certains aspects du jeu,
en terme d'asymétrie des distributions au bridge induisant des manoeuvres spectaculaires hors-normes.
Elle est prépondérante ici.

Enfin une question probabiliste qui enfonce le clou si je puis dire, une sorte de mariage géant:
Quelle est la probabilité que chaque tas ait des cartes de même hauteur: l'un quatre As , un autre quatre 2, etc.
On suppose toutes les répartitions équiprobables.

Autre question annexe:
On distribue les cartes, faces cachées.
Puis on en découvre un tas, on on constate 4 cartes identiques , puis on continue avec à chaque fois la même constatation.
Quel est est le minimum de tas à découvrir pour pouvoir être sûr que le lemme des mariages va être vérifié ?
Si par exemple on a ouvert 11 tas, et qu'il ne reste plus que les Rois et les Dames avec deux tas cachés...

Bonne investigation!

Dernière modification par bridgslam (07-07-2025 07:40:31)