Le problème des mariage

par **Ben314** » 21 Juil 2010, 12:02

Bon, ça rame... (c'est normal, c'est quand même pas évident...)
Je donne un début de vague "indic" concernant la solution que je connais :
On fait effectivement une récurrence et, dans l'hérédité, dés le départ, on considère deux cas de figure que l'on traite différement.

par **nodjim** » 22 Juil 2010, 15:19

Je n'ai pas encore pu mettre en défaut cette stratégie: On marie, un à un, et dans cet ordre, le garçon qui connait le moins de filles. Bien sûr, à chaque mariage, il faut remettre à jour le nombres de connaissances libres de chaque garçon, avant de faire le nouveau choix.

par **Doraki** » 22 Juil 2010, 15:22

G1 : F1,F2
G2 : F2,F3
G3 : F3,F4
G4 : F2,F3,F4

Je prends G1, et je le marie avec F2.
A toi de poursuivre.

par **nodjim** » 22 Juil 2010, 15:34

Doraki a écrit:G1 : F1,F2
G2 : F2,F3
G3 : F3,F4
G4 : F2,F3,F4

Je prends G1, et je le marie avec F2.
A toi de poursuivre.

Ah oui, bien sûr....

par **Ben314** » 22 Juil 2010, 15:59

nodjim a écrit:Je n'ai pas encore pu mettre en défaut cette stratégie: On marie, un à un, et dans cet ordre, le garçon qui connait le moins de filles. Bien sûr, à chaque mariage, il faut remettre à jour le nombres de connaissances libres de chaque garçon, avant de faire le nouveau choix.

Trois garçons G1,G2,G3 trois filles F1,F2,F3.
G1 connait F1 et F2
G2 connait F1 et F2
G3 connait F1 et F3
Je commence par "celui qui connait le moins de filles" donc au pif, je commence par G3 et je le marie au pif par exemple avec F1 => c'est foutu !

par **nodjim** » 25 Juil 2010, 09:51

Un truc qui a l'air de marcher:
On examine un à un les liens de connaissance. Si un lien testé n'est ni le dernier de la fille, ni le dernier du garçon, on l'élimine, sinon on le garde définitivement.
Il me semble qu'avec cette méthode, on ne peut pas aboutir, à un moment quelconque de l'avancement, à une surjection (plus de garçons que de filles restants), car c'est proscrit par la contrainte de départ, et que les liens ultimes n'ont pas été supprimés.

par **Ben314** » 25 Juil 2010, 09:55

Qu'appelle tu le "dernier" lien ?

par **Doraki** » 25 Juil 2010, 09:56

G1 : F1, F3
G2 : F1, F2
G3 : F3, F4
G4 : F3, F4

J'examine que je peux retirer le lien G1-F1 vu que G1 a encore F3 et F1 a encore G2.
Donc je garde G1-F3 vu que c'est le dernier de G1.
Ensuite je suis forcé de prendre G2-F1 vu que c'est le dernier de F1.
Puis G3-F4 vu que c'est le dernier de G3.
Et G4 peut rien faire.

par **nodjim** » 25 Juil 2010, 10:21

Doraki a écrit:G1 : F1, F3
G2 : F1, F2
G3 : F3, F4
G4 : F3, F4

J'examine que je peux retirer le lien G1-F1 vu que G1 a encore F3 et F1 a encore G2.
Donc je garde G1-F3 vu que c'est le dernier de G1.
Ensuite je suis forcé de prendre G2-F1 vu que c'est le dernier de F1.
Puis G3-F4 vu que c'est le dernier de G3.
Et G4 peut rien faire.

Vite démonté mon truc!

Le problème des mariage

Qui est en ligne