Laboratoire des contradictions logiques

Résolvez une nouvelle énigme dont l'unique réponse a été vérifiée par recherche exhaustive.

Exemple résolu — Laboratoire des contradictions logiques

Résolues	0 / 0
Mondes possibles	8 sur 8 restent
Chaîne de déduction	0/3 équations appliquées

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Une énigme est un système d'équations booléennes

Codez le véridique par 1 et le menteur par 0. Un locuteur est cohérent si la valeur de sa phrase égale son bit de rôle.

S_X(R) = R_X

Le laboratoire vérifie Sₓ(R) = Rₓ pour chaque X. Toutes les équations partagent le même vecteur R et doivent tenir ensemble.

Chaque phrase est une fonction booléenne de l'attribution complète.

Une contradiction élimine tout un monde possible

Supposez une attribution, évaluez chaque phrase et comparez le résultat au rôle du locuteur.

S_X(R) ≠ R_X ⇒ reject R

Un seul écart suffit à rejeter l'attribution. Les indices nomment l'hypothèse et l'équation qui rend sa branche impossible.

La contradiction démontre qu'un monde ne peut satisfaire les règles.

Être soluble ne suffit pas : la réponse doit être unique

Une énigme peut être cohérente tout en ayant plusieurs attributions valides.

|{R : ∀X, S_X(R)=R_X}| = 1

Chaque énigme est vérifiée exhaustivement et acceptée seulement si un seul monde survit.

Le monde vert est l'unique modèle du système.

Les indices forts éliminent beaucoup de mondes

Une phrase utile partage les candidats ; une faible vaut pareil dans presque tous.

candidates: 2ⁿ → … → 1

Le moteur choisit l'équation non appliquée qui retire le plus de mondes : il réduit l'incertitude sans donner directement la réponse.

Les candidats diminuent avec les équations informatives.

L'autoréférence n'est pas automatiquement utile

« Je dis la vérité » convient aux deux rôles et n'apporte aucune information.

S_X(R) = R_X

« Je mens » ne peut être dit de façon cohérente par aucun rôle strict. Le générateur exclut les deux formes et utilise des relations entre participants.

Une autoaffirmation est tautologique ; l'autre crée une équation impossible.

Problèmes entièrement résolus

Trois participants sous les règles Chevalier/Valet choisissant entre des affectations 7 étapes
Trois participants selon les règles Chevalier/Menteur : l'affirmation d'un Chevalier doit être vraie, celle d'un Menteur doit être fausse. Le laboratoire propose une nouvelle énigme à chaque visite, résolvez donc celle-ci sur papier — A dit que C ment ; B dit que A et C ont le même rôle ; C dit qu'au moins 2 d'entre nous disent la vérité. Avant de désigner qui que ce soit, comptez les attributions entre lesquelles vous hésitez, puis réduisez-les une phrase après l'autre.
1. Aucune hypothèse n'est faite sur le nombre de Chevaliers : chaque participant est donc un bit indépendant : Chevalier 1, Menteur 0. Un monde est le vecteur complet de 3 bits, et chacun d'eux est initialement valide. C'est le nombre sur lequel s'ouvre le panneau des mondes, et c'est une propriété de la distribution des rôles, non de ce que quiconque a dit.
  
  $2^{3} = 8$
2. Une phrase n'est pas un fait concernant la pièce ; c'est une équation concernant son locuteur. La phrase du locuteur X est une fonction booléenne du vecteur complet des rôles R, et la cohérence exige que sa valeur de vérité soit égale au bit propre de X — vraie pour un Chevalier, fausse pour un Menteur, une équation dans les deux cas. Les 3 équations partagent le même R, c'est pourquoi vous ne pouvez pas déterminer A, puis B, puis C séparément.
  
  $S_{X} (R) = R_{X}, X \in {A, B, C}$
3. Commençons par A. Si A est un Chevalier, la phrase se vérifie et C ment ; si A est un Menteur, la phrase échoue et C dit la vérité. Les deux branches laissent A et C avec des bits différents, ce qui représente 4 des 8 mondes, B restant libre.
  
  $R_{A} = \neg R_{C} ⟹ 8 \to 4$
4. B affirme que A et C ont le même rôle. Ce n'est pas le cas, donc la phrase de B est fausse, et B est donc un Menteur. Deux mondes subsistent : A Chevalier avec C Menteur, ou A Menteur avec C Chevalier.
  
  $R_{B} = [R_{A} = R_{C}] = 0 ⟹ 4 \to 2$
5. C tranche la question. Dans les deux mondes survivants, exactement 1 participant dit la vérité, la proposition au moins 2 d'entre nous est donc fausse, et le bit propre de C doit donc être 0. Le monde où C est un Chevalier affirme une chose que son propre rôle interdit et disparaît. Il ne reste qu'un monde.
  
  $Σ R = 1 < 2 ⟹ S_{C} = 0 ⟹ R_{C} = 0$
6. Revenons en arrière et demandons-nous pourquoi A et B ont chacun éliminé exactement la moitié. Aucune de leurs phrases ne mentionne son propre locuteur : ainsi, pour chaque configuration des 2 autres bits, il existe exactement 1 valeur du bit du locuteur qui satisfait l'équation. Une phrase portant sur les autres laisse toujours 2^n-1 mondes — ni plus, ni moins, peu importe ce qu'elle dit.
  
  $R_{X} = S_{X} (R_{- X}) ⟹ 2^{n - 1} = 2^{2} = 4$
7. La phrase de C n'est pas de cette nature : au moins 2 d'entre nous compte également C, le bit du locuteur se trouve donc des deux côtés de l'équation et l'argument de la division par deux s'effondre. Appliquée seule à l'ensemble des 8 mondes, l'équation de C en laisse 6 — elle élimine 2 mondes là où celles de A et de B en éliminent chacune 4.
  
  $# {R : R_{C} = S_{C} (R)} = 6 \neq = 4$
Réponse

A est un Chevalier, B et C sont des Menteurs — 1 monde sur les 8 sur lesquels s'ouvre le panneau. L'unicité relève de l'arithmétique plutôt que de la chance : 3 locuteurs qui ne parlent chacun que des autres divisent le domaine par deux 3 fois, et si les réductions sont indépendantes, 2³ divisé par deux 3 fois donne exactement 1. C'est pourquoi dans les énigmes de ce type, tout le monde parle de tout le monde. C fait exception, et cela a un coût : une équation qui compte son propre locuteur laisse 6 mondes sur 8 au lieu de 4, de sorte qu'elle nettoie un quart du plateau là où les autres en nettoient la moitié. On peut calculer ce nombre pour n'importe quelle phrase candidate avant même de connaître un seul rôle, ce qui en fait la mesure honnête d'un indice — non pas sa subtilité apparente, mais la quantité du plateau qu'il élimine.

$2^{n} \cdot (\frac{1}{2})^{n} = 1$
Quatre participants dans un thème Loup-garou comptant les mondes viables 6 étapes
Même laboratoire, thème Loup-garou, 4 participants. Exactement 1 des 4 est le Loup-garou, et le Loup-garou est le seul qui ment. Comptez les mondes possibles avant que quiconque ne parle, puis comparez ce résultat avec la manche des Chevaliers à 3 participants.
1. Les rôles sont toujours des bits — Villageois 1, Loup-garou 0 — et 4 bits libres donneraient 16 vecteurs. C'est le nombre que le thème doit battre.
  
  $2^{4} = 16$
2. Le thème est une contrainte, pas un décor : exactement 1 bit vaut 0. Choisir quel bit vaut 0 revient à choisir 1 participant parmi 4, de sorte que seuls 4 des 16 vecteurs conviennent. La grille des mondes les énumère, le W unique se déplaçant d'une position sur chaque ligne.
  
  $(1 4) = 4$
3. Réduire l'espace d'un facteur 4 équivaut à 2 bits, et ils vous ont été fournis avant qu'un mot ne soit prononcé.
  
  $lo g_{2} \frac{16}{4} = 2$
4. Voici maintenant la comparaison qui importe. La manche des Chevaliers avec 3 participants s'ouvre sur 8 mondes ; cette manche comporte un suspect supplémentaire et s'ouvre sur 4. Plus de personnes, mais une recherche plus restreinte — l'a priori l'emporte sur le bit ajouté par le participant supplémentaire.
  
  $2^{3} = 8 > 4$
5. Un seul menteur signifie aussi exactement 1 mensonge. Les 4 participants parlent tous et seule la phrase du Loup-garou est fausse, de sorte que 3 des 4 phrases à l'écran sont vraies — ce que vous savez avant d'en lire la moindre.
  
  $# {X : R_{X} = 0} = 1 ⟹ # {X : S_{X} (R) = 0} = 1$
6. Ce qui rend la force brute réellement peu coûteuse ici : 4 mondes multipliés par 4 équations de locuteurs représentent 16 vérifications de cohérence, et vous pourriez les faire sur papier. Les mêmes 4 personnes sous les règles Chevalier/Menteur donneraient 16 mondes multipliés par 4 équations, soit 64.
  
  $4 \times 4 = 16 2^{4} \times 4 = 64$
Réponse

4 sur 4, et non 16 sur 16 — le thème a supprimé 75 % du plateau avant la première phrase. À plus grande échelle, les deux jeux cessent d'être le même jeu. Avec n participants, l'espace du Loup-garou est n et l'espace des Chevaliers est 2ⁿ : à 10 joueurs, cela fait 10 mondes contre 1024, et l'a priori vaut désormais 10 − log₂10 = 6,68 bits. La raison en est qu'une manche du Loup-garou ne demande jamais que lequel, de sorte que sa réponse est d'une largeur d'au plus log₂ n bits quel que soit le nombre de chaises ajoutées, tandis qu'une manche des Chevaliers pose n questions indépendantes par oui ou par non et double chaque fois que quelqu'un s'assied. Ajouter un joueur à une manche du Loup-garou ajoute 1 monde ; en ajouter un à une manche des Chevaliers les double.

$\frac{2 ^{n}}{n}_{n = 10} = \frac{1024}{10} = 102.4$

Références (1)

The book that made logic something you can compute with, which is what this lab does: G. Boole, An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities. Walton and Maberly, London, 1854.

Par l’équipe 42Math · Mis à jour 2026-07-22

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Mathématiques →

Laboratoire des contradictions logiques

Exemples de problèmes