Se marier avec quelqu’un qu’on aime
Comment trouver l’amour de sa vie ? Comment se caser ? Comment former un bon couple ? Ce type de questions préoccupe beaucoup de gens. Voici une version matheux de ce problème fondamentale.
Le problème de mariage ou le problème de former les bons couples
Supposons que nous avons n femmes et n hommes, tous célibataires et prêts à se marier ; pour tout entier k dans [1,n] et tout choix de k femmes, l’ensemble des hommes qui sont aimés par au moins une de ces femmes contient au moins k éléments.
Démontrer qu’on peut organiser des mariages tels que chaque femme se marie avec un époux qu’elle aime.
Ce n’est pas trop difficile de faire une demonstration par recurrence sur n, mais la formulation mathematique du probleme me semble peu conforme a la realite car suppose que l’on organise des "mariages arranges" a grande echelle (par contre, le modele est realiste si on veut organiser un emploi du temps).
Voici un autre modele :
on se donne n hommes et n femmes. Chaque homme aime un certain nombre de femmes, qu’il classe par ordre de preference. Chaque femme aime un certain nombre d’hommes, qu’elle classe par ordre de preference. Les hommes ne sont pas au courant des preferences des femmes, mais connaissent les preferences des autres hommes. Chaque homme choisit de courtiser une femme, et si une femme est courtisee par plusieurs hommes qu’elle aime, elle va se marier avec celui qu’elle prefere. Quelle strategie doit adopter un homme qui veut maximiser ses chances de trouver une epouse des la premiere tentative?
> Ce n’est pas trop difficile de faire une demonstration par recurrence sur n
Dire « trop difficile » c’est relatif. En tout cas cla solution que j’ai trouvée ne me semble pas si simple, sauf si je suis passé à côté d’une astuce…
Voici donc une esquisse de solution :
on suppose que l’assertion est vraie pour tout n'<n.
Pour tout ensemble E de femmes, on note h(E) l’ensemble des hommes qui sont aimés par au moins l’une des femmes parmi E. Soit donc F un ensemble de n femmes et H un ensemble de n hommes tels que pour toute partie X de F on ait #h(X) >= #X.
Premier cas : il existe une partition \(A\cup B\) de F telle que #A=#h(A). Soient A’=h(A) et soit B’=H-A’. On vérifie facilement que (A,A’) et (B,B’) satisfont l’hypothèse de récurrence, donc on peut marier chaque femme de A avec un homme dans A’ et chaque femme de B avec un homme de B’.
Deuxième cas : pour tout \(\emptyset \ne A\subset F\) tel que \(A\ne F\) on a #h(A)>#A. Choisissons une femme f et un homme h qu’elle aime. On les marie ensemble. Soit F’=F-{f} et H’=H-{h}, alors (F’,H’) satisfont l’hypothèse de récurrence, donc on peut marier toute femme de F’ avec un homme dans H’.
Oui, c’est aussi ma solution !