Sujet
Friends
Imaginons un groupe de 7 amis étudiants : Rachel, Monica, Ross, Chandler, Janice, Joe et Phoebe.Ils habitent New York et projettent de louer deux voitures pour aller passer des vacances en Floride. Chaque voiture peut transporter au maximum quatre personnes, chauffeur compris.
Toutefois, passer ensemble les 18 heures que dure le trajet peut s'avérer problématique si les occupants de chaque voiture ne sont pas soigneusement choisis. En effet, il faut savoir que :
(1) Rachel et Ross viennent de rompre; il ne serait donc pas judicieux qu'ils voyagent ensemble.
(2) Joe est amoureux de Rachel, il y a donc des tensions entre lui et Ross.
(3) Phoebe tente d'attirer l'attention de Joe, mais celui-ci la repousse.
(4) Chandler vient juste de piquer à Joe la place de capitaine de l'équipe de foot, et il en résulte un certain ressentiment.
(5) Monica et Chandler sont jaloux de Janice, parce que, malgré un talent discutable (selon eux), elle est premier violon à l'orchestre de l'université alors qu'eux ne sont que seconds violons.
(6) Monica pense que Joe n'est pas très malin.
- Trouver une répartition des sept étudiants dans les deux voitures qui respecte ces différentes incompatibilités. Est-ce la seule possible?
- L'un des sept étudiants décide de rester en Floride. On constate alors qu'il y a quatre répartitions possibles pour le retour des six autres étudiants. Qui est resté en Floride et quelles sont les répartitions possibles pour le retour?
- Soient A et B les deux voitures et A celle de Rachel. Ross doit donc être dans B , Joe dans A , Phoebe dans B, Chandler dans B, Janice dans A et Monica dans B.
- Construisons le graphe ayant pour sommets les sept étudiants et pour arêtes les incompatibilités:
Si c'est Joe qui reste en Floride, Chandler et Monica doivent être dans la même voiture et Janice dans l'autre, Rachel et Ross dans deux voitures différentes, soit deux possibilités, Phoebe peut alors choisir l'une des voitures, soit encore deux possibilités, soit en tout quatre possibilités.