mathématiques (Première S, Liban) · Chapitre 16 · Exercice de TD
Principe additif, principe multiplicatif et itinéraires en étapes
Arrangements et permutations · A. Principe multiplicatif et notation factorielle · niveau 2
Énoncé
Un réseau routier relie trois villes , et . Il existe ~routes distinctes reliant directement à (notées ), ~routes distinctes reliant directement à (notées ), et ~routes côtières reliant directement à sans passer par (notées ).
1) Combien existe-t-il d'itinéraires différents pour aller de à (en passant ou non par ) ?
2) Combien existe-t-il d'itinéraires aller-retour passant par à l'aller comme au retour ?
3) Combien existe-t-il d'itinéraires aller-retour n'empruntant au retour aucune des deux routes utilisées à l'aller ?
Corrigé
La stratégie. On distingue soigneusement le connecteur « ou » entre deux familles disjointes de trajets (qui relève du principe additif) et le connecteur « puis » entre les étapes successives d'un même trajet (qui relève du principe multiplicatif).
1) Trajets aller simple de à . L'ensemble des itinéraires de à est la réunion disjointe de deux sous-ensembles :
- les itinéraires passant par , composés du choix d'une route de à (~choix) puis d'une route de à (~choix), soit ~itinéraires par le principe multiplicatif ;
- les itinéraires directs de à sans passer par , au nombre de . D'après le principe additif, le nombre total d'itinéraires de à est :
2) Aller-retour via sans contrainte. Le voyage se décompose en ~étapes successives : (~choix), (~choix), (~choix) et (~choix). Par le principe multiplicatif :
3) Aller-retour via sans réutiliser les routes de l'aller.
- À l'aller, il y a toujours ~choix pour et ~choix pour .
- Au retour, la route empruntée entre et à l'aller est interdite : il ne reste que ~choix pour l'étape . De même, la route empruntée entre et à l'aller est interdite : il reste ~choix pour l'étape . Par le principe multiplicatif :
Ce que l'exercice installe. Lorsqu'une procédure comporte à la fois des alternatives qui s'excluent (« passer par » ou « prendre la route côtière ») et des étapes successives (« aller de à » puis « aller de à »), on applique le principe multiplicatif à l'intérieur de chaque alternative, puis on additionne les cardinaux des alternatives disjointes.
Exercices semblables
- Simplifications factorielles, sommes télescopiques et équations en corrigé
- Nombres de quatre chiffres avec contraintes de parité et d'ordre corrigé
- Tirages successifs de jetons et passage au complémentaire corrigé
- Permutations avec blocs groupés et alternance de catégories corrigé
- Anagrammes avec répétitions et contraintes sur les extrémités corrigé