Sujet
On donne ici le plan simplifié d'un lycée :
- Jean est le gardien du lycée. Le matin, Jean doit allumer toutes les lumières du lycée avant l'arrivée des élèves.
a) Il part du Hall 2, est-il possible qu'il parcoure tout l'établissement sans avoir à passer deux fois par la même pièce?
Où finira-t-il ? (On ne s'occupe pas de savoir comment Jean
entre ou sort de l'établissement)
Si oui, représenter un tel trajet sur le plan du lycée donné en annexe 1.
b) Un tel parcours est- il possible si Jean part du Bâtiment 2 ? Pourquoi ? - A la fin de la journée, Jean doit vérifier qu'il ne reste personne dans l'établissement. Pour cela, dès qu'il entre dans une pièce, il ferme la porte qu'il vient de passer à clef, traverse la pièce puis ferme à clef la porte qu'il vient d'utiliser pour sortir de la pièce.
On ne s'occupe toujours pas de savoir comment Jean entre ou sort de l'établissement.
En partant dans le Hall 1 et en terminant dans le Bâtiment 1, est-il possible que Jean parcoure tout l'établissement sans avoir à ré-ouvrir une porte déjà fermée ?
Si oui, représenter son parcours sur le plan donné en annexe 2. - Le proviseur du lycée décide de refaire les peintures des murs de l'établissement de plusieurs couleurs différentes. Il souhaite que deux salles voisines (c'est- à- dire avec une porte en commun) aient des couleurs différentes et se demande alors combien de couleurs il va devoir utiliser au minimum.
Pour l'aider dans sa recherche, on a représenté le plan du lycée à l'aide d'un graphe :
Chaque pièce du lycée est représentée par un sommet (par exemple le sommet A représente l'administration) et les arêtes représentent les différentes portes pour communiquer entre les pièces.
On va donc attribuer une couleur à chaque sommet de sorte que deux sommets reliés par une arête ne soient pas de la même couleur, et ce avec le moins de couleurs possibles.
a) En considérant les sommets A , H et C , expliquer pourquoi le proviseur doit choisir au moins trois couleurs différentes.
b) Colorier alors les trois sommets A, C et H. On va ensuite essayer de n'utiliser que ces trois couleurs pour le reste du lycée.
c) Quelle doit être la couleur du sommet B ? Et du sommet G ?
d) En suivant le même raisonnement "de proche en proche" déterminer une couleur pour chaque sommet du graphe.
e) Finalement, quel est le nombre minimal de couleurs que doit choisir le proviseur ?
f) A l'aide du nombre de portes et donc d'arêtes pour chaque sommet, identifier chaque sommet à une pièce du lycée.
Aucun corrigé disponible pour cet exercice dans la source APMEP.