Lemme des mariages

Dénombrements et probabilités -- Dénombrement

Théorème : Soient F et G deux ensembles finis, et soit f une application de G dans P(F). On suppose que pour toute partie X de G, le cardinal de est de cardinal supérieur à celui de X. Alors il existe une application injective M de G dans F tel que M(g) est élément de f(g) pour tout g.

  Voici l'interprétation cupidonesque de ce théorème. G désigne un ensemble de garçons, F désigne un ensemble de filles, et f est l'application qui à chaque garçon associe l'ensemble des filles qui lui plaise. Alors, si pour chaque sous-groupe de garçons, l'ensemble des filles qui leur plait est plus grand 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!

Version imprimable


Pour signaler une erreur, proposer une amélioration, contacter les auteurs, écrivez à
La BibM@th 2000-2013 - V&F Bayart