Bibm@th

Lemme des mariages

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!