II-5. Notice 2 : Le logicien.

II-4. Notice 1 : Deviner le nombre choisi

Notice 2

Le logicien, les saints et les menteurs

II-6. Notice 3 : Le jeu des sept allumettes

Le logicien, les saints et les menteurs

1° Analyse du problème.
Les lampes $X$ , $Y$ , $Z$ allumées (resp. éteintes) indiquent que la 1 $^{\grave{e}re}$ personne interrogée, la 2 $^{\grave{e}me}$ , la 3 $^{\grave{e}me}$ sont des saints (resp. des menteurs). La clé du problème tient au fait que le logicien connait la réponse donnée par la 1 $^{\grave{e}re}$ personne sans qu’il soit nécessaire de comprendre celle-ci. En effet : si cette personne est un saint elle dit « je suis un saint » ; si cette personne est un menteur, elle… ment et elle dit « je suis un saint ». Autrement dit, la première personne répond toujours « je suis un saint ».

$\begin{tabular}{|c|c|c||c|c|c|} \multicolumn{3}{c}{\textsf{\large{}$\begin{array}{c} entr\acute{e}e\\ \overbrace{\qquad\qquad} \end{array}$}} & \multicolumn{3}{c}{\textsf{\large{}$\begin{array}{c} sortie\\ \overbrace{\qquad\qquad} \end{array}$}}\tabularnewline \hline \textsf{\large{}A} & \textsf{\large{}B} & \textsf{\large{}C} & \textsf{\large{}X} & \textsf{\large{}Y} & \textsf{\large{}Z}\tabularnewline \hline 1 & 1 & 1 & 1 & 1 & 1\tabularnewline \hline 1 & 1 & 0 & 0 & 1 & 0\tabularnewline \hline 1 & 0 & 1 & 0 & 1 & 1\tabularnewline \hline 1 & 0 & 0 & 1 & 1 & 0\tabularnewline \hline 0 & 1 & 1 & 0 & 0 & 0\tabularnewline \hline 0 & 1 & 0 & 1 & 0 & 1\tabularnewline \hline 0 & 0 & 1 & 1 & 0 & 1\tabularnewline \hline 0 & 0 & 0 & 0 & 0 & 1\tabularnewline \hline \end{tabular}$

Ceci conduit à la Table de valeurs ci-dessus. En effet :

Table de valeurs.

— Si, par exemple, la 2 $^{\grave{e}me}$ personne interrogée répond « le 1 $^{er}$ a dit qu’il est un menteur » on inscrit $A=0$ , mais on sait qu’alors cette deuxième personne ment, donc $Y=0$ , ce qui permet de remplir de 0 les quatre dernières lignes de la colonne $Y$ ;
— si, ensuite, la 3 $^{\grave{e}me}$ personne interrogée répond « le 1 $^{er}$ est un menteur » (c’est-à-dire $B=0$ ) et « le deuxième est un menteur » (c’est-à-dire $C=0$ ), cette dernière phrase comparée au renseignement connu (la 2 $^{\grave{e}me}$ personne est effectivement un menteur) assure que cette 3 $^{\grave{e}me}$ personne est un saint (donc $Z=1$ ) et, par suite, ce qui est vrai, « la 1 $^{\grave{e}re}$ est un menteur » ( $X=0$ ). Ceci nous permet de remplir la dernière ligne de la table.
— On procède de même pour les huit lignes. Ainsi pour $A=1$ , $B=1$ , $C=0$ (2 $^{\grave{e}me}$ ligne). $\begin{tabular}{rcl} $A=1$ & : & {\small{}La 2$^{\grave{e}me}$ personne dit }\textbf{\small{}« la 1$^{\grave{e}re}$a dit qu'il est un saint »}{\small{}. C'est vrai.}\tabularnewline & & {\small{}Donc cette deuxième personne est un saint (Y = 1). }\tabularnewline $B=1$ & : & {\small{}La 3$^{\grave{e}me}$ personne dit }\textbf{\small{}« la 1$^{\grave{e}re}$ personne est un saint »}{\small{}.}\tabularnewline $C=0$ & : & {\small{}La 3$^{\grave{e}me}$ personne dit }\textbf{\small{}« la 2$^{\grave{e}me}$ personne est un menteur ».}{\small{} C'est faux. }\tabularnewline & & {\footnotesize{}Donc cette 3$^{\grave{e}me}$ personne ment ($Z=0$) et par suite la 1$^{\grave{e}re}$ est un }\textbf{\footnotesize{}menteur}{\footnotesize{}. }\tabularnewline \end{tabular}$
3° Expressions algébriques.
- — La lampe $X$ doit être allumée ( $X=1$ ) sur les « lignes» 1, 4 , 6, 7 correspondant à :
  $\begin{tabular}{cc} & ($A=1$ et $B=1$ et $C=1$) \tabularnewline \textbf{ou} & ($A=1$ et $B=0$ et $C=0$) \tabularnewline \textbf{ou} & ($A=0$ et $B=1$ et $C=0$) \tabularnewline \textbf{ou} & ($A=0$ et $B=0$ et $C=1$) \tabularnewline \end{tabular}$ c’est-à-dire : $\left|\begin{array}{c} ABC\\ A\;\overline{B}\;\overline{C}\\ \overline{A}B\overline{C}\\ \;\overline{A}\;\overline{B}C \end{array}\right|$
- — De même (lignes 1, 2, 3, 4 de la table) : $\left|\begin{array}{c} ABC\\ AB\overline{C}\\ A\overline{B}C\\ A\;\overline{B}\;\overline{C} \end{array}\right|$
- — De même (lignes 1, 3, 6, 8 de la table) : $\qquad\qquad\left|\begin{array}{c} ABC\\ A\overline{B}C\\ \overline{A}B\overline{C}\\ \;\overline{A}\;\overline{B}\;\overline{C} \end{array}\right|$
Donc $\qquad X=\left|\begin{array}{c} ABC\\ A\;\overline{B}\;\overline{C}\\ \overline{A}B\overline{C}\\ \;\overline{A}\;\overline{B}C \end{array}\right|\qquad \qquad Y=\left|\begin{array}{c} ABC\\ AB\overline{C}\\ A\overline{B}C\\ A\;\overline{B}\;\overline{C} \end{array}\right|\qquad \qquad Z=\left|\begin{array}{c} ABC\\ A\overline{B}C\\ \overline{A}B\overline{C}\\ \;\overline{A}\;\overline{B}\;\overline{C} \end{array}\right|$
4° Simplifications (voir 1 $^{\grave{e}re}$ partie, § 6 et 8). $X$ ne peut être simplifiée. Donc :
$X=\left|\begin{array}{c} ABC\\ A\;\overline{B}\;\overline{C}\\ \overline{A}B\overline{C}\\ \;\overline{A}\;\overline{B}C \end{array}\right| \qquad \qquad Y=\left|\begin{array}{c} ABC\\ AB\overline{C}\\ A\overline{B}C\\ A\;\overline{B}\;\overline{C} \end{array}\right|= A\left|\begin{array}{c} B\\ \overline{B} \end{array}\right|=A \qquad \qquad Z=\left|\begin{array}{c} ABC\\ A\overline{B}C\\ \overline{A}B\overline{C}\\ \;\overline{A}\;\overline{B}\;\overline{C} \end{array}\right|=\left|\begin{array}{c} AC\\ \;\overline{A}\;\overline{C} \end{array}\right|$

5° Schéma du programme (voir notice $\fbox{2}$ ).

— Pour « alimenter » la lampe $X$ , il est nécessaire (puisqu’il y a quatre ou) de la relier à quatre « colonnes de programmation ». Nous avons choisi les colonnes 1, 2, 3, 4.Sur la colonne 1, nous avons mis $\;\overline{A}\;\overline{B}C$ (fiches à droite sur les barrettes A et B, fiche à gauche sur la barrette C). Sur la colonne 2, nous avons mis $\overline{A}B\overline{C}$ . Sur la colonne 3, il y a $A\;\overline{B}\;\overline{C}$ Sur la colonne 4, il y a $ABC$
— Pour « alimenter » la lampe $Y$ , il suffit d’une seule « colonne de programmation ». Nous avons choisi la colonne 5. Pour « écrire » $A$ , il suffit de placer une fiche à gauche de la colonne 5, sur la barrette $A$ et de « neutraliser» $B$ et $C$ en plaçant deux fiches de part et d’autre de la colonne 5 sur les barrettes $B$ et $C$ .
— Pour la lampe Z, il faut deux colonnes. Nous avons choisi les colonnes de programmation 6 et 7. Sur la colonne 6, nous avons placé $\;\overline{A}\;\overline{C}$ ; sur la colonne 7, $AC$
— Ainsi est justifié le programme présenté sur la notice $\fbox{2}$ .