Problème — Chemins sur un réseau quadrillé

Application directe du cours · niveau 2 · mathématiques (terminale), chapitre 7 — Combinatoire et Dénombrement

Énoncé

Problème — Chemins sur un réseau quadrillé.

On considère un réseau quadrillé du plan. Un chemin minimal reliant le point $O (0, 0)$ au point $M (a, b)$ , où $a$ et $b$ sont des entiers naturels, est constitué d'une succession de pas unitaires : soit vers la droite (noté D, incrémentant l'abscisse de 1), soit vers le haut (noté H, incrémentant l'ordonnée de 1).

Justifier qu'un tel chemin comporte exactement $a + b$ pas, dont $a$ pas vers la droite. En déduire que le nombre total de chemins possibles est $(a a + b)$ .
On pose $a = 5$ et $b = 4$ . Calculer le nombre de chemins reliant $(0, 0)$ à $(5, 4)$ .
On impose de passer par le point d'étape $A (2, 2)$ . Combien de chemins reliant $(0, 0)$ à $(5, 4)$ passent par $A$ ?
Combien de chemins ne passent pas par $A$ ?
Combien de chemins reliant $(0, 0)$ à $(5, 4)$ passent par le point $A (2, 2)$ ou par le point $B (3, 3)$ ?

Corrigé

Pour se rendre de $O (0, 0)$ à $M (a, b)$ par des déplacements minimaux, on doit nécessairement effectuer exactement $a$ pas vers la droite (pour atteindre l'abscisse $a$ ) et $b$ pas vers le haut (pour atteindre l'ordonnée $b$ ). Le nombre total de pas est donc $a + b$ . Un chemin est entièrement caractérisé par l'emplacement des $a$ pas vers la droite parmi les $a + b$ pas totaux. Le nombre de façons de choisir ces emplacements est donné par la combinaison :

$(a a + b)$

(qui est égal par symétrie à $(b a + b)$ , c'est-à-dire le choix des pas vers le haut).

Pour $a = 5$ et $b = 4$ , le nombre de chemins possibles est :

$(5 5 + 4) = (5 9) = \frac{9 \times 8 \times 7 \times 6 \times 5}{5 \times 4 \times 3 \times 2 \times 1} = 126$

Un chemin passant par $A (2, 2)$ est composé :

d'un chemin de $O (0, 0)$ à $A (2, 2)$ : ici $a_{1} = 2$ et $b_{1} = 2$ , ce qui donne $(2 2 + 2) = (2 4) = 6$ chemins ;
d'un chemin de $A (2, 2)$ à $M (5, 4)$ : le déplacement requis est de $5 - 2 = 3$ pas vers la droite et $4 - 2 = 2$ pas vers le haut, soit $(3 3 + 2) = (3 5) = 10$ chemins.

Par le principe multiplicatif, le nombre de chemins de $O$ à $M$ passant par $A$ est :

$N_{A} = (2 4) \times (3 5) = 6 \times 10 = 60$

Le nombre de chemins ne passant pas par $A$ est le complémentaire du nombre de chemins passant par $A$ :

$N_{A ˉ} = Total - N_{A} = 126 - 60 = 66$

Soit $C_{A}$ l'ensemble des chemins passant par $A$ et $C_{B}$ l'ensemble des chemins passant par $B$ . On cherche $Card (C_{A} \cup C_{B})$ . D'après le principe additif :

$Card (C_{A} \cup C_{B}) = Card (C_{A}) + Card (C_{B}) - Card (C_{A} \cap C_{B})$

On a déjà $Card (C_{A}) = 60$ .
Calculons $Card (C_{B})$ : de $O (0, 0)$ à $B (3, 3)$ , $(3 3 + 3) = (3 6) = 20$ chemins ; de $B (3, 3)$ à $M (5, 4)$ (déplacement de $2$ vers la droite et $1$ vers le haut), $(2 2 + 1) = (2 3) = 3$ chemins. D'où $Card (C_{B}) = 20 \times 3 = 60$ .
Calculons $Card (C_{A} \cap C_{B})$ , c'est-à-dire les chemins passant par $A$ ET par $B$ . Comme $A (2, 2)$ est situé avant $B (3, 3)$ , un tel chemin va de $O$ à $A$ ( $(2 4) = 6$ chemins), puis de $A$ à $B$ ( $(1 1 + 1) = 2$ chemins), puis de $B$ à $M$ ( $(2 3) = 3$ chemins). Ainsi $Card (C_{A} \cap C_{B}) = 6 \times 2 \times 3 = 36$ .

On en déduit :

$Card (C_{A} \cup C_{B}) = 60 + 60 - 36 = 84$

Il y a 84 chemins qui passent par $A$ ou par $B$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.