site2wouf.fr : La tournée du jour

Les mathématiciens manipulent parfois de grands nombres, mais jamais dans leurs revenus.

Isaac Asimov (sur Mon tshirt!)

Partager :

Facebook X (Twitter) LinkedIn Email WhatsApp

🔑 Code de cette fiche :

imprimer LaTeX
ℹ️

Besoin d'aide sur les graphes et le critère d'Euler ?

Consultez la page du catalogue pour retrouver le critère d'Euler et le raisonnement sur la parité des degrés.

📚 Voir les ressources pédagogiques

Fiche n°
Sujet complémentaire

Le plan du quartier et les trois questions :

La tournée du facteur

Voici le plan d'un quartier. Les lettres désignent les carrefours, les traits les rues. Il y a 9 rues en tout : [AC], [AD], [AE], [BC], [BD], [BE], [CD], [CE], [DE].
ABCDE
Le facteur voudrait emprunter chaque rue exactement une fois — ni deux fois la même, ni en oublier. Il peut passer plusieurs fois par un même carrefour, cela ne le dérange pas.
Les questions se suivent : la première n'est qu'un comptage, la dernière demande une preuve.
  1. Pour chaque carrefour, compter le nombre de rues qui y aboutissent. Présenter les résultats dans un tableau.
  2. Le facteur imagine sa tournée. À chaque fois qu'il traverse un carrefour, combien de rues utilise-t-il ? Qu'en déduire pour les carrefours où aboutit un nombre impair de rues ?
  3. La tournée est-elle possible ? Si oui, en donner une en précisant le point de départ ; si non, le démontrer.

Un cahier d'exercices de 128 pages ...

Le cahier : 5,40 €

Plus de Produits

Publicité

Corrigé :

La tournée du facteur — Correction

1. On compte les rues aboutissant à chaque carrefour :
CarrefourABCDE
Nombre de rues33444
Paritéimpairimpairpairpairpair
Vérification : la somme de ces nombres vaut 18 = 2 × 9, car chaque rue est comptée à ses deux extrémités.
Les carrefours à nombre impair de rues sont : A, B — il y en a 2.
2.
Le raisonnement clé. Quand le facteur traverse un carrefour, il y arrive par une rue et en repart par une autre : il consomme les rues deux par deux. Un carrefour traversé 3 fois voit donc 6 de ses rues utilisées — toujours un nombre pair.
Un carrefour où aboutit un nombre impair de rues ne peut donc pas être seulement traversé : il doit être le départ ou l'arrivée de la tournée. Là, une rue reste « non appariée ».
Or une tournée n'a qu'un seul départ et une seule arrivée. Il ne peut donc pas y avoir plus de deux carrefours impairs.
3.
C'est possible, mais à une condition : il faut partir de A et arriver en B (ou l'inverse) — les deux carrefours impairs.
Un itinéraire possible :
A → D → B → E → A → C → E → D → C → B
ABCDE
Le plan : les 9 rues sont toutes parcourues une fois par cet itinéraire.
Cet itinéraire comporte 9 étapes, soit exactement les 9 rues, chacune une seule fois.
Attention au point de départ. Partir d'un carrefour pair condamnerait la tournée : on peut vérifier qu'aucun itinéraire complet ne commence ailleurs qu'en A ou B.
Le critère d'Euler, à retenir. Si le plan est d'un seul tenant, la tournée est possible si et seulement si le nombre de carrefours impairs vaut 0 (on revient au départ) ou 2 (on part de l'un et on finit à l'autre). Dans tous les autres cas, c'est impossible.
Un peu d'histoire. Ce problème est né à Königsberg en 1736 : les habitants cherchaient une promenade franchissant les sept ponts de la ville une seule fois chacun. Euler démontra que c'était impossible — les quatre quartiers avaient tous un nombre impair de ponts. C'est l'acte de naissance de la théorie des graphes.

Des centaines de PDF disponibles gratuitement !

Pour accéder à nos ressources gratuites, il vous suffit de sélectionner l'activité que vous désirez dans le formulaire au dessus de l'activité du jour. Ensuite, utilisez l'icône appropriée sous les liens de partage pour télécharger vos PDF.

N'oubliez pas, partager fait vivre les sites ! 😊 Merci de votre soutien !

🔗 Liens utiles

// Remarques, codes, note de version etc...

J'ai réalisé cette activité en Python, en utilisant xhtml2pdf pour la version PDF des activités. Mon travail est sous licence Creative commons.

La version actuelle est la version 3.2.0 (28/11/2023)

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