Ce site utilise Google Analytics, Google AdSense et le service de chat Crisp pour mesurer l'audience, afficher des annonces et proposer une assistance en ligne. Acceptez-vous le dépôt de cookies ?
Même si vous jouez la perfection, une faute de votre adversaire peut détruire toute la beauté de la partie.
Vladimir Kramnik ( Nouveau design ! )
🔑 Code de cette fiche :
| Les rues | ⑨ quai aux Fleurs | Ⓐ Carrefour de l'Hôpital | Ⓙ Rond-point du Stade |
| ① rue des Lilas | ⑩ chemin Creux | Ⓑ Rond-point de la Gare | Ⓚ Place Sainte-Croix |
| ② rue du Puits | ⑪ rue Pasteur | Ⓒ Place des Tanneurs | Ⓛ Place du Vieux-Puits |
| ③ rue des Jardins | ⑫ allée des Peupliers | Ⓓ Carrefour du Lavoir | Les bâtiments |
| ④ passage du Marché | ⑬ venelle du Chat | Ⓔ Place de la Fontaine | a l'école |
| ⑤ allée des Tilleuls | ⑭ rue Verte | Ⓕ Carrefour des Tilleuls | b la pharmacie |
| ⑥ sentier des Prés | ⑮ chemin du Lavoir | Ⓖ Carrefour de la Mairie | c le lavoir |
| ⑦ rue de l'Église | ⑯ chemin des Vignes | Ⓗ Place du Marché | d la salle des fêtes |
| ⑧ rue du Stade | Les carrefours | Ⓘ Rond-point des Vaches |
Explorez l'intégralité de la collection. Chaque problème donne le plan d'un quartier : le car scolaire part de l'école et doit s'arrêter à chaque carrefour exactement une fois. Deux questions par fiche — avec retour à l'école, puis sans.
📍 Vous consultez actuellement le problème n°260
Ces 400 problèmes posent la même question devant des plans toujours différents : le car scolaire, parti de l'école, peut-il s'arrêter à chaque carrefour exactement une fois ? Puis la même, sans l'obligation de revenir.
Tout part d'un coloriage en damier : deux carrefours reliés par une rue ne reçoivent jamais la même couleur. Le car change alors de couleur à chaque trajet, et ses arrêts alternent. Un circuit exige donc autant de carrefours de chaque couleur ; une tournée sans retour en tolère un de plus, mais elle doit alors partir et arriver sur cette couleur-là.
Chaque fiche est accompagnée d'une correction complète au format PDF, plan colorié et trajet détaillé compris, ainsi que de sa source LaTeX.
🔢 Le raisonnement, en une phrase : chaque rue relie un carrefour sombre à un carrefour clair, donc le car change de couleur à chaque trajet. Une tournée qui dessert tous les carrefours en utilise autant de chaque couleur, à un près — et un circuit, qui revient à son point de départ, en utilise exactement autant.
✉️ Les séries jumelles : sur des plans du même genre, La tournée du facteur demande de parcourir chaque rue une fois, et sa version sans retour lève l'obligation de rentrer. Là, compter les parités décide ; ici, compter les couleurs ne peut que réfuter. C'est toute la différence entre Euler et Hamilton.
🎓 Utilisation pédagogique : une entrée idéale vers la théorie des graphes, accessible dès la 5ᵉ car elle ne demande que de compter et de raisonner sur la parité. Les élèves les plus en difficulté avec le calcul y réussissent souvent très bien.
🌉 Pourquoi il n'y a pas de critère : passer par tous les carrefours est un problème dit hamiltonien, et personne ne connaît de règle qui le décide à coup sûr — c'est l'un des problèmes réputés difficiles de l'informatique. Les fiches de cette série sont choisies pour que la réponse soit toujours démontrable en classe : par le coloriage, ou par un carrefour dont le retrait couperait le quartier en morceaux.
Ce problème est un chemin (ou circuit) hamiltonien : on passe par chaque sommet une fois. Les articles ci-dessous, publiés sur le blog, vont au-delà du programme du collège — ils sont là pour préparer la séance, pas pour être donnés aux élèves.
Le générateur de cette activité (html, svg, tex et pdf) est écrit en Python 3 ; les PDF sont composés avec LaTeX et les figures sont vectorielles. Mon travail est sous licence Creative commons.
N'hésitez pas à me contacter si vous detectez la moindre imperfection, ou si vous imaginez une amélioration potentielle !
Open source et gratuité n'empêchent ni les dons ni les remerciements 😉
Un euro ou deux pour m'aider à payer le serveur ?
☕ Payez-moi un café via PayPal
Partager :
🔑 Accéder à une fiche par son code
Demande le code à ton professeur.
Exemples : PYTH0123, PMDE161842, SOMP0042.