mathématiques (Première S, Liban) · Chapitre 16 · Exercice de TD
Codification et logistique au port de Beyrouth
Arrangements et permutations · C. Permutations, placements et anagrammes · niveau 3 (difficile)
Énoncé
Le terminal logistique du port de Beyrouth attribue à chaque conteneur enregistré un identifiant alphanumérique de ~caractères, composé successivement :
- d'un préfixe de zone formé de ~lettres majuscules choisies parmi l'ensemble (~lettres) ;
- suivi d'un numéro de série formé de ~chiffres choisis parmi l'ensemble (~chiffres).
Partie A — Capacité d'adressage selon les règles de codage. 1) Calculer le nombre total d'identifiants possibles si les répétitions de lettres et de chiffres sont autorisées. 2) Pour éviter les erreurs de saisie optique, une nouvelle norme impose que les ~lettres du préfixe soient distinctes et que les ~chiffres du numéro de série soient deux à deux distincts. Calculer le nombre d'identifiants conformes à cette norme. 3) Parmi les identifiants de la norme sans répétition :
- a) Combien commencent par la lettre et se terminent par le chiffre ?
- b) Combien contiennent au moins une fois le chiffre ?
- c) Combien ont leurs quatre chiffres rangés dans l'ordre strictement croissant de gauche à droite (par exemple ) ? (Indication : on pourra commencer par compter combien de permutations de ~chiffres distincts fixés les rangent dans l'ordre croissant.)
Partie B — Organisation d'une travée de stockage. Sur un quai, une travée comporte ~emplacements alignés numérotés de à , destinés à recevoir ~conteneurs tous différents (portant des identifiants distincts ). Chaque emplacement peut recevoir au plus un conteneur (les ~emplacements restants demeurent vides). 4) De combien de façons différentes peut-on placer ces ~conteneurs sur les ~emplacements de la travée ? 5) Trois de ces conteneurs () sont des conteneurs frigorifiques qui doivent obligatoirement être branchés sur les ~premiers emplacements ( ou ), seuls équipés de prises électriques, tandis que les trois autres conteneurs () peuvent occuper n'importe lesquels des emplacements restants. Combien de placements respectent cette contrainte technique ?
Corrigé
La stratégie. Dans la partie A, le préfixe littéral et le numéro de série numérique sont choisis indépendamment : le nombre total d'identifiants est le produit du nombre de préfixes par le nombre de numéros de série. Dans la question 3c, l'observation clé est que, pour un ensemble fixé de ~chiffres distincts, une seule des ~permutations de ces ~chiffres est rangée dans l'ordre strictement croissant. Dans la partie B, placer ~conteneurs distincts dans ~emplacements revient à choisir pour chaque conteneur son numéro d'emplacement sans répétition : c'est un arrangement .
Partie A — Capacité d'adressage. 1) Avec répétition. Le préfixe est une -liste de (~choix) et le numéro de série est une -liste de (~choix). Par le principe multiplicatif :
2) Norme sans répétition. Le préfixe est un arrangement de ~lettres parmi (~choix) et le numéro de série est un arrangement de ~chiffres parmi (~choix) :
3) Dénombrements sous la norme sans répétition.
- a) Si la première lettre est fixée à (~choix), il reste ~choix dans pour la seconde lettre. Si le dernier chiffre est fixé à (~choix), les ~premiers chiffres forment un arrangement de ~chiffres parmi , soit ~choix. D'où :
- b) Le nombre d'identifiants sans répétition qui ne contiennent aucun chiffre s'obtient en choisissant les ~chiffres distincts parmi les ~chiffres , soit . Par passage au complémentaire dans les identifiants :
- c) Les ~suites de ~chiffres deux à deux distincts se regroupent par paquets de ~suites utilisant exactement les quatre mêmes chiffres permutés dans tous les ordres possibles. Dans chaque paquet de ~permutations, une seule et unique suite range ces quatre chiffres dans l'ordre strictement croissant. Il y a donc ~suites strictement croissantes de ~chiffres. En multipliant par les ~préfixes littéraux :
Partie B — Organisation de la travée. 4) Placement sans contrainte. Attribuer à chacun des ~conteneurs un emplacement distinct parmi les ~emplacements de la travée revient à former un arrangement de ~emplacements choisis parmi :
5) Placement avec contrainte sur les conteneurs frigorifiques.
- 1ʳᵉ étape : on place les ~conteneurs frigorifiques sur ~emplacements distincts choisis parmi les ~emplacements équipés . Le nombre de choix est .
- 2ᵉ étape : une fois ces ~conteneurs placés, il reste exactement ~emplacements libres sur la travée (le quatrième emplacement équipé non utilisé et les ~emplacements ordinaires à ) pour accueillir les ~conteneurs restants . Le nombre de façons de les placer est . Par le principe multiplicatif, le nombre de placements conformes est :
Ce que l'exercice installe. Deux idées essentielles se dégagent de ce problème : d'une part, diviser un nombre d'arrangements par permet de compter les suites strictement croissantes (ou les choix où l'ordre est imposé d'avance) ; d'autre part, lorsqu'un sous-groupe d'objets est soumis à une restriction d'emplacement, on place toujours ce sous-groupe en premier avant de placer les objets non restreints dans la totalité des places restantes.
Exercices semblables
- Principe additif, principe multiplicatif et itinéraires en étapes 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é