Énigmes classiques — Logique & Culture générale
Apprendre à repérer l'espace d'états, les invariants et les stratégies de résolution qui rendent les énigmes classiques systématiques et résolubles.
Énigmes classiques — Logique & Culture générale
Public: niveau Libre — objectif: savoir analyser et résoudre les énigmes les plus fréquentes.
Objectifs
- Reconnaître le type d'énigme (logique, combinatoire, probabilité, optimisation).
- Choisir une stratégie (recherche d'états, invariants, retour en arrière, comptage).
- Rédiger une solution claire et vérifiable.
Quel est le premier réflexe utile face à une énigme de type "transport" (ex: traverser une rivière) ?
Notions clés
Espaces d'états et recherche
On représente chaque configuration possible (positions des objets, du bateau, du gardien, etc.). On cherche un chemin dans ce graphe d'états du départ vers l'objectif. Deux algorithmes conceptuels utiles : parcours en largeur (BFS) pour trouver la solution la plus courte, et parcours en profondeur (DFS) pour explorer rapidement.
Combinatoire élémentaire
Permutations et combinaisons permettent de compter les possibilités sans énumérer :
Permutation de n objets: \[ n! = 1 \cdot 2 \cdots n \]
Combinaison: \(\binom{n}{k} = \dfrac{n!}{k!(n-k)!}\) — utile pour évaluer l'espace de solutions possibles.
Invariants et parité
Un invariant est une propriété qui ne change pas sous les actions autorisées. Par exemple, dans certains jeux de pièces, la parité du nombre d'échanges reste constante : si une action change la parité, la situation finale peut être impossible.
Raisonnement rétrograde (work backward)
Commencez de l'objectif et remontez les actions possibles; souvent plus simple que de partir du début.
Parmi ces méthodes, laquelle aide le mieux à prouver l'impossibilité d'une configuration ?
Exemples résolus
1) Le loup, la chèvre et le chou (traversée)
Vous avez un loup, une chèvre et un chou. Le bateau transporte une seule chose en plus du fermier. Le loup ne peut pas rester seul avec la chèvre, la chèvre ne peut pas rester seule avec le chou. Comment traverser ?
Voir la solution
Succession: chèvre → retour → loup → chèvre retour → chou → retour → chèvre (opérations reprises ci-dessus).
Étape 1: Emmener la chèvre isolant loup et chou.
Étape 3: Transporter ensuite le loup et ramener la chèvre, etc.
2) Le problème de Monty Hall
Trois portes, une voiture, deux chèvres. Vous choisissez une porte; l'animateur ouvre une autre porte montrant une chèvre et vous propose de changer. Faut-il changer ?
Voir la solution
En affichant :
\[P(\text{win if switch}) = \frac{2}{3}\]
3) Le pont (bridge and torch)
Quatre personnes doivent traverser un pont la nuit avec une seule lampe; au plus deux traversent à la fois, et ils vont aux vitesses a<b<c<d (minutes). Quelle stratégie minimise le temps total ?
Voir la solution
Par exemple, pour \(a=1, b=2, c=5, d=10\):
\[T_1 = 1 + 2\times 2 + 10 = 15\]
\[T_2 = 2\times 1 + 5 + 10 = 17\]
Donc la stratégie 1 est meilleure ici (15 min).
Dans l'exemple ci-dessus (1,2,5,10), quel est le temps minimal ?
Que représente un "état" dans la modélisation d'une énigme ?
Erreurs fréquentes
- Ne pas définir clairement les états (on confond parfois position du bateau et position des objets).
- Oublier de vérifier que les actions respectent toutes les contraintes.
- Ne pas tester la solution pour quelques cas simples avant de la généraliser.
Quelle est une bonne façon d'éviter les oublis dans une solution ?
Récapitulatif
Pour résoudre une énigme classique: modélisez, cherchez des invariants, comparez stratégies, testez sur des exemples simples et rédigez clairement.
Quelle stratégie est la plus générale pour aborder une énigme ?
Teste tes connaissances sur ce cours
Crée ton compte gratuitement pour accéder aux quiz associés et suivre ta progression.