CH/DEN - Dénombrer des chemins

Dans cette famille de problèmes, la tâche essentielle est de trouver le nombre de chemins sur un quadrillage (ou un graphe) en respectant quelques contraintes: extrémités fixées, nombre de pas, type de croisement, point intermédiaires, etc.

Remarque et suggestion

Problèmes

Maman (ral. 03.I.08 ; cat. 3-5 ; 03rmti_fr-8): Dénombrer des chemins formant le mot "maman" sur une grille de lettres.

Journée sportive (ral. 04.I.01 ; cat. 3-3 ; 04rmti_fr-1): Dénombrer des parcours dans un petit labyrinthe (régulier).

Tous les chemins mènent à ... B ! (ral. 06.I.07 ; cat. 3-8 ; 06rmti_fr-7): Dénombrer le nombre de chemins reliant les deux extrémités d'un quadrillages 4 x 3. Les chemins doivent suivre le quadrillage sans recul.

La toile (ral. 07.II.14 ; cat. 7-8 ; 07rmtii_fr-14): Déterminer sur un réseau en toile d'araignée les chemins les plus courts entre deux noeuds donnés.

Yogi l'ours (ral. 08.II.03 ; cat. 3-5 ; 08rmtii_fr-3): Déterminer le nombre de façon de parcourir un graphe orienté formé de 3 sommets et 5 arêtes en passant une et une seule par chaque arête.

Fontaines (ral. 11.I.01 ; cat. 3-3 ; 11rmti_fr-1): Déterminer le nombre de façon de parcourir un certain graphe formé de 5 sommets et 7 arêtes en passant une et une seule par chaque arête

Fourmis sur un filet (ral. 18.F.04 ; cat. 3-5 ; 18rmtf_fr-4): Déterminer tous les chemins les plus courts possibles entre deux points d'un réseau rectangulaire.

Le réseau hexagonal de Rosalie (ral. 19.F.12 ; cat. 6-8 ; 19rmtf_fr-12): Dénombrer un nombre de chemins dans un réseau hexagonal.

Chemin d'allumettes (ral. 22.F.03 ; cat. 3-5 ; 22rmtf_fr-3): Trouver tous les chemins qui peuvent être tracés sur une portion de quadrillage en se déplaçant uniquement vers le haut ou vers la droite.

De la nourriture pour tous! (ral. 31.F.03 ; cat. 3-5 ; 31rmtf_fr-3): Répertorier tous les parcours différents partant d’un point, reliant les 5 nœuds d’un réseau sans passer deux fois par le même et revenant au point de départ.