Ces problèmes donnent souvent beaucoup de phrases pour peu de places. Leur secret est graphique : convertir chaque contrainte en un symbole court, puis propager les conséquences.
Les quatre formats principaux
| Format | Représentation utile |
|---|---|
| Ordre linéaire | Cases numérotées ou ligne |
| Placement circulaire | Cercle avec un repère fixe |
| Affectation | Tableau personnes × postes |
| Ensembles | Diagramme d'Euler-Venn |
Traduire les contraintes
- « A avant B » :
A < B. - « B immédiatement après A » : bloc
[A B]. - « C n'est pas à côté de D » : interdire
CDetDC. - « E entre F et G » :
F < E < GouG < E < Fselon le sens. - « Une seule personne par poste » : éliminations croisées dans le tableau.
Une contrainte d'immédiateté est plus forte qu'une simple contrainte d'ordre. Placez d'abord les blocs, les extrémités et les positions fixes.
La méthode BLOC
- Bâtir la grille ou les cases.
- Lister les contraintes fortes.
- Occuper les positions certaines et éliminer.
- Contrôler chaque contrainte avant de conclure.
Ordre linéaire
Supposons cinq livres : blanc, rouge, vert, bleu, jaune.
- le vert suit immédiatement le rouge ;
- le blanc est avant le rouge ;
- le bleu est après le vert ;
- le jaune est après le bleu.
Le bloc [rouge vert] impose l'ordre unique : blanc, rouge, vert,
bleu, jaune.
Placement circulaire
En cercle, les rotations produisent des dispositions équivalentes. Fixez une personne en haut pour supprimer cette symétrie. Précisez aussi si « à droite » signifie droite immédiate et dans quel sens le cercle est lu.
Tableau d'affectation
Pour trois personnes et trois missions, utilisez des croix et des coches. Chaque certitude élimine une ligne et une colonne.
Diagrammes de Venn
Trois questions dominent :
- inclusion : A est-il entièrement dans B ?
- intersection : existe-t-il des éléments communs ?
- exclusion : les ensembles sont-ils disjoints ?
Optimisation
Un problème d'optimisation demande le meilleur résultat sous contraintes : coût minimal, durée minimale, distance minimale, nombre maximal. Commencez par définir précisément la quantité à optimiser, puis comparez les seules solutions admissibles.
Entraînement
Quatre personnes A, B, C, D sont alignées. B est immédiatement à droite de A. C est à droite de B. D est à gauche de A. Ordre ?
Le bloc AB est précédé par D et suivi par C. Ordre : D-A-B-C.
Cinq livres blanc, rouge, vert, bleu, jaune sont rangés. Vert est immédiatement après rouge ; blanc avant rouge ; bleu après vert ; jaune après bleu. Ordre ?
Blanc-Rouge-Vert-Bleu-Jaune.
A, B, C et D courent. A arrive avant C. B arrive immédiatement après A. D arrive après C. Classement ?
Le bloc AB doit précéder C, puis D. Classement : A-B-C-D.
Trois réunions X, Y, Z ont lieu à 9 h, 10 h et 11 h. X n'est pas à 9 h. Y est avant X. Z n'est pas à 11 h. Affectation ?
Si X=10 h, Y=9 h et Z=11 h, mais Z ne peut pas être 11 h. Donc X=11 h, Y=10 h ou 9 h. Comme Z n'est pas 11 h, deux solutions restent : Y=9 h/Z=10 h ou Z=9 h/Y=10 h. L'affectation n'est pas unique.
Ajoutez à l'exercice précédent : Z est avant Y. Quelle affectation devient unique ?
Z=9 h, Y=10 h, X=11 h.
Trois personnes Lina, Marc et Nora choisissent Paris, Lyon et Lille. Lina ne choisit pas Paris. Marc choisit Lyon. Nora ne choisit pas Lille. Une destination par personne. Solution ?
Marc=Lyon. Restent Paris et Lille. Nora ne peut pas Lille, donc Nora=Paris et Lina=Lille.
Cinq sièges numérotés 1 à 5. A est au siège 3. B est à gauche de A. C est à droite de A. D est immédiatement à gauche de E. Donnez une disposition possible.
Aucune disposition n'est possible. A occupe la place 3. Si le bloc D-E occupe les places 1-2, il ne reste aucune place à gauche de A pour B. S'il occupe les places 4-5, il ne reste aucune place à droite de A pour C.
Tous les ingénieurs sont diplômés. Certains diplômés sont musiciens. Représentez les ensembles. Peut-on placer nécessairement des ingénieurs dans les musiciens ?
Le cercle ingénieurs est inclus dans diplômés. Musiciens intersecte diplômés. On ne sait pas si cette intersection touche ingénieurs. Non.
Aucun chat n'est un reptile. Certains animaux sont des chats. Que montre le diagramme ?
Chats et reptiles sont disjoints. Une croix « certains animaux » est placée dans la zone chats. Ces animaux ne sont donc pas reptiles.
Une tournée doit visiter A, B et C depuis le dépôt D. Distances : D-A=4, D-B=2, D-C=5, A-B=3, A-C=2, B-C=4. Quel circuit D puis trois villes puis D est le plus court ?
Comparer les circuits distincts : D-A-C-B-D = 4+2+4+2 = 12. D-B-A-C-D = 2+3+2+5 = 12. Les autres sens équivalents donnent aussi ces valeurs ou davantage. Le minimum est 12, avec au moins deux circuits équivalents.
Trois tâches durent 2 h, 3 h et 4 h. Deux personnes peuvent travailler en parallèle, une seule tâche par personne. Durée minimale ?
Répartir 4 h sur une personne et 3 h+2 h=5 h sur l'autre. Durée minimale : 5 h.
A n'est pas en première position. B est avant A. C n'est pas en dernière position. Parmi trois positions, trouvez l'ordre.
B doit être avant A. Si A=2, B=1 et C=3, mais C ne peut pas être dernier. Donc A=3. B et C occupent 1 et 2, sans autre contrainte : B-C-A ou C-B-A. Deux solutions.
Ajoutez : B est immédiatement avant A. Quel ordre devient possible ?
Le bloc BA en positions 1-2 placerait C en position 3, ce qui est interdit. Il doit donc occuper les positions 2-3. Ordre : C-B-A.
Trois candidats A, B, C passent à 9 h, 10 h, 11 h. A n'est pas à 9 h ; B passe avant A ; C n'est pas à 11 h. Donnez toutes les solutions.
Si A=10 h, B=9 h et C=11 h, interdit. Donc A=11 h. B et C peuvent occuper 9 h et 10 h dans les deux ordres. Solutions : B9-C10-A11 et C9-B10-A11.
Le test de cohérence final
Avant de valider une disposition :
- relisez chaque contrainte une à une ;
- distinguez « avant » de « immédiatement avant » ;
- vérifiez l'unicité si la question demande « l'ordre » ;
- si plusieurs solutions restent, ne fabriquez pas une certitude ;
- pour une optimisation, confirmez que la solution est admissible avant de comparer son coût.
Questions fréquentes
Que faire quand il y a beaucoup de contraintes ?
Classez-les : positions fixes, blocs immédiats, extrémités, exclusions, puis simples relations d'ordre.
Une question peut-elle ne pas avoir de solution ?
Oui, surtout dans les exercices de cohérence. Une contradiction peut être la réponse attendue.
Comment savoir si une solution est unique ?
Après avoir trouvé une disposition, cherchez volontairement une autre disposition compatible. Si elle existe, la réponse n'est pas unique.