Pousse-pousse sur un graphe - Lycée Guy Moquet (Chateaubriant)
Titre du sujet:
Pousse-pousse sur un graphe
Établissement:
- Lycée Guy Moquet (Chateaubriant)
Année:
- 2014-2015
Résumé:
On considère un graphe avec n+1 sommets numérotés de 0 a n, tel que chaque sommet
du graphe soit relié a exactement 3 autres sommets. On prend n jetons, numérotés de
1 a n et on les places arbitrairement sur n sommets du graphe. Peut-on faire en sorte
de remettre chaque jeton sur le sommet de même numéro, en s'autorisant uniquement a
faire glisser un jeton sur une arrête vers un sommet vide ?