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 ?
La meilleure preuve qu'il existe une forme d'intelligence extraterrestre est qu'elle n'a pas essayé de nous contacter.
🔑 Code de cette fiche :
| Les rues | ⑨ rue des Lilas | Ⓑ Place aux Herbes | Ⓚ Placette des Ormes |
| ① impasse des Cerisiers | ⑩ venelle du Chat | Ⓒ Fontaine Notre-Dame | Ⓛ Carrefour de la Mairie |
| ② rue Pasteur | ⑪ sentier des Prés | Ⓓ Rond-point des Vaches | Les bâtiments |
| ③ quai aux Fleurs | ⑫ rue du Moulin | Ⓔ Place de la Fontaine | a l'école |
| ④ rue du Stade | ⑬ rue Basse | Ⓕ Place de l'Église | b le stade |
| ⑤ passage du Marché | ⑭ rue du Pont | Ⓖ Rond-point du Stade | c la bibliothèque |
| ⑥ rue du Four | ⑮ chemin de Ronde | Ⓗ Rond-point de la Poste | d l'église |
| ⑦ chemin du Lavoir | Les carrefours | Ⓘ Place du Vieux-Puits | |
| ⑧ boulevard du Parc | Ⓐ Coin du Lavoir | Ⓙ Carrefour des Tilleuls |
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°263
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.