Exercice 3

Sujet

Vingt six étudiants : Anissa, Boris, Charly, Damien, Elisa, Florian, Gautier, Hélène, Iris, Justine, Kevin, Laura, Maureen, Nathalie, Ophélie, Pascal, Quentin, Rose, Steve, Thibault, Ursule, Victor, William et Xavier Yann et Zoé sont inscrits en TD de Mathématiques et doivent former des groupes.
Ils font part de leurs souhaits de groupe à l'administration sous la forme suivante : ( \(\mathrm{A}, \mathrm{D}\) ), ( \(\mathrm{A}, \mathrm{F}\) ), ( \(\mathrm{E}, \mathrm{P}\) ), \((\mathrm{G}, \mathrm{L}),(\mathrm{G}, \mathrm{R}),(\mathrm{G}, \mathrm{T}),(\mathrm{C}, \mathrm{H}),(\mathrm{I}, \mathrm{H}),(\mathrm{M}, \mathrm{H}),(\mathrm{S}, \mathrm{N}),(\mathrm{U}, \mathrm{V}),(\mathrm{F}, \mathrm{Q})\) et \((\mathrm{Y}, \mathrm{V})\).
Par exemple, (A,D) signifie qu'Anissa aimerait être dans le même groupe que Damien.

1. En tenant compte des souhaits de chacun, quel est le nombre minimal de groupes de TD à former pour que tous les étudiants soient satisfaits?
2. L'administration décide de faire plutôt de plus petits groupes et plus nombreux.
   a) Si \(x\) désigne un étudiant, alors on note \(f(x)\) l'ensemble des étudiants qui devraient figurer dans le même groupe que \(x\) d'après les vœux, soit parce qu'ils ont demandé x , soit parce que \(x\) les a demandés.
   Par exemple, \(f(\mathrm{~A})=\mathrm{D}, \mathrm{F}\) et \(f(\mathrm{H})=\mathrm{C}, \mathrm{I}, \mathrm{M}\).
   Déterminer tous les \(f(x)\).
   On pourra présenter les résultats dans un tableau de la forme :

b) Un étudiant est dit «isolé » s'il n'a demandé à être avec personne et si personne n'a demandé à être avec lui c'est-à-dire si \(f(x)=\varnothing\).
Comment peut on alors satisfaire tous les étudiants, même ceux qui sont isolés?
3. On considère alors l'algorithme suivant :

a) Que permet de faire cet algorithme ?
b) Exécuter cet algorithme pour Xavier puis pour Gautier.
c) Combien faut-il alors de groupes pour que tous les étudiants soient satisfaits ?