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. nombre de chemins = C(p+q,q)
  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 5 + 3 = 8 pas 👉 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 : C(8,3) = (8 × 7 × 6)/(3!) = 336/6 = 56 chemins ℹ️ On aurait pu compter les positions des → : C(8,5) = C(8,3) = 56 — même résultat, par symétrie. Choisir où mettre les ↑ ou où mettre les → revient au même.

    C(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 C(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 C(5,2) = (5 × 4)/2 = 10 chemins Par le principe multiplicatif — chaque début peut se prolonger par chaque fin : 3 × 10 = 30 chemins passant par C 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.

    C(3,1) × C(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.