Chemins sur un quadrillage

Énoncé

Sur un quadrillage, on part du point A(0,0) pour aller au point B(5,3). On ne peut se déplacer que d'un pas vers la droite (→) ou d'un pas vers le haut (↑). a) Combien de pas faut-il pour aller de A à B ? b) Combien de chemins différents mènent de A à B ? c) Parmi ces chemins, combien passent par le point C(2,1) ?

Indice : a) Compter les déplacements nécessaires. b) Un chemin = une suite de R et H → choisir les positions des H. c) Chemins A→C multipliés par chemins C→B.

Correction

1. Étape 1 : Un problème qui paraît géométrique et qui est purement combinatoire — c'est tout l'intérêt de le voir. 👉 La traduction décisive : un chemin n'est rien d'autre qu'une suite de pas, donc un mot écrit avec deux lettres, → et ↑. Compter les chemins revient à compter ces mots. Et compter les mots est facile : il suffit de choisir les positions des ↑ parmi toutes les positions disponibles. Les → occupent automatiquement le reste. Chemins sur un quadrillage : De (0,0) à (p,q) : p+q pas au total, dont q vers le haut. [formule]
2. Étape 2 : a) Pour aller de A(0,0) à B(5,3) : il faut avancer de 5 en abscisse 5 pas vers la droite et de 3 en ordonnée 3 pas vers le haut [formule] 👉 Ce nombre ne dépend pas du chemin : tous les trajets font exactement 8 pas, puisqu'aucun retour en arrière n'est autorisé. C'est ce qui rend le comptage possible.

   5 + 3 = 8 pas

3. Étape 3 : b) Un chemin est une suite de 8 pas, dont exactement 3 sont des ↑. Le décrire revient à choisir les 3 positions (parmi les 8) occupées par les ↑ — les 5 autres étant nécessairement des →. L'ordre de ce choix n'a pas d'importance (on désigne un ensemble de positions), donc c'est une combinaison : [formule] ℹ️ On aurait pu compter les positions des → : 8{5} = 8{3} = 56 — même résultat, par symétrie. Choisir où mettre les ↑ ou où mettre les → revient au même.

   8{3} = 56 chemins

4. Étape 4 : c) Un chemin passant par C(2,1) se décompose en deux morceaux indépendants : de A(0,0) à C(2,1) : 2 pas → et 1 pas ↑, soit 3 pas dont 1 vers le haut 3{1} = 3 chemins de C(2,1) à B(5,3) : il reste 5-2 = 3 pas → et 3-1 = 2 pas ↑, soit 5 pas dont 2 vers le haut 5{2} = 5 4{2} = 10 chemins Par le principe multiplicatif — chaque début peut se prolonger par chaque fin : [formule] Contrôle : 30 < 56 ✓ — passer par un point imposé est une contrainte, donc cela réduit. ℹ️ Et 30{56} 54\,\% : un peu plus d'un chemin sur deux passe par C, ce qui est plausible pour un point situé à peu près sur la diagonale du rectangle.

   3{1} 5{2} = 30

5. Étape 5 : L'erreur classique : Additionner les deux morceaux en c) : 3 + 10 = 13. Chaque début se combine avec chaque fin : il y a 3 façons d'arriver en C et, pour chacune, 10 façons d'en repartir. C'est un « et », donc une multiplication. 👉 Second piège : recompter les pas du second morceau à partir de zéro au lieu de soustraire les coordonnées de C. De C(2,1) à B(5,3), il reste 5-2 pas horizontaux et 3-1 verticaux — pas 5 et 3. À retenir : Un chemin est un mot en → et ↑ : le compter revient à choisir les positions d'une des deux lettres. 👉 Et un point de passage imposé découpe le trajet en deux problèmes indépendants, dont les résultats se multiplient.