Défis de logique

Allume le premier interrupteur pendant quelques minutes, puis éteins-le. Allume ensuite le deuxième et entre immédiatement dans la pièce.

Si l’ampoule est allumée, c’est le deuxième interrupteur. Si elle est éteinte mais chaude, c’est le premier. Si elle est éteinte et froide, c’est le troisième.

Pioche un fruit dans la boîte étiquetée « Pommes + Oranges ». Comme son étiquette est fausse, cette boîte contient un seul type de fruit.

Si tu tires une pomme, cette boîte est donc la boîte Pommes. La boîte étiquetée « Oranges » ne peut pas contenir des oranges puisque son étiquette est fausse ; elle ne peut pas non plus contenir seulement des pommes puisque cette catégorie vient d’être identifiée. Elle contient donc le mélange. La dernière boîte contient alors les oranges.

Le raisonnement est exactement symétrique si le fruit tiré est une orange.

Au départ, allume la première corde aux deux extrémités et la seconde à une seule extrémité.

La première corde se consume en exactement 30 minutes. À cet instant, allume l’autre extrémité de la seconde corde. Il lui restait alors 30 minutes de combustion si elle avait continué par un seul bout ; brûlée désormais par les deux bouts, elle finit en 15 minutes.

Total : 30 + 15 = 45 minutes.

Une stratégie optimale est :

1. 1 et 2 traversent : 2 min.
2. 1 revient avec la torche : 1 min.
3. 7 et 10 traversent ensemble : 10 min.
4. 2 revient avec la torche : 2 min.
5. 1 et 2 traversent : 2 min.

Total : 2 + 1 + 10 + 2 + 2 = 17 minutes.

Forme trois groupes de 3 pièces.

Première pesée : compare le groupe A au groupe B. Si la balance est équilibrée, la fausse pièce est dans C. Sinon, elle est dans le plateau le plus léger.

Il reste donc exactement 3 candidates. Deuxième pesée : prends deux de ces trois pièces et compare-les. Si elles s’équilibrent, la troisième est fausse. Sinon, la plus légère des deux est la fausse.

Numérote les pièces de 1 à 12.

Pesée 1 : compare 1,2,3,4 à 5,6,7,8.

Cas A — équilibre.
La fausse est parmi 9,10,11,12 et les pièces 1,2,3 sont normales.
Pesée 2 : compare 9,10,11 à 1,2,3.
• Si équilibre : 12 est fausse. Pesée 3 : 12 contre 1 indique si elle est lourde ou légère.
• Si 9,10,11 sont plus lourdes : l’une d’elles est trop lourde. Pesée 3 : 9 contre 10 ; la plus lourde est fausse, ou 11 si équilibre.
• Si 9,10,11 sont plus légères : même raisonnement ; la plus légère entre 9 et 10 est fausse, ou 11 si équilibre.

Cas B — le plateau 1,2,3,4 est plus lourd.
Les possibilités sont alors : 1,2,3,4 trop lourdes ou 5,6,7,8 trop légères. La pièce 9 est normale.
Pesée 2 : compare 1,2,5 à 3,6,9.
• Si le plateau gauche est plus lourd : suspects = 1 lourde, 2 lourde, 6 légère. Pesée 3 : 1 contre 2. La plus lourde est fausse ; si équilibre, 6 est légère.
• Si équilibre : suspects = 4 lourde, 7 légère, 8 légère. Pesée 3 : 7 contre 8. Si équilibre, 4 est lourde ; sinon la plus légère des deux est fausse.
• Si le plateau droit est plus lourd : suspects = 3 lourde ou 5 légère. Pesée 3 : 3 contre 9. Si 3 est plus lourde, c’est elle ; sinon 5 est légère.

Cas C — le plateau 5,6,7,8 est plus lourd.
C’est le cas symétrique : 1,2,3,4 peuvent être trop légères ou 5,6,7,8 trop lourdes.
On refait la même pesée 2 : 1,2,5 contre 3,6,9.
• Si le plateau gauche est plus lourd : suspects = 3 légère ou 5 lourde. Pesée 3 : 3 contre 9.
• Si équilibre : suspects = 4 légère, 7 lourde, 8 lourde. Pesée 3 : 7 contre 8.
• Si le plateau droit est plus lourd : suspects = 1 légère, 2 légère, 6 lourde. Pesée 3 : 1 contre 2.

Dans chaque branche, la troisième pesée identifie sans ambiguïté la pièce et la nature de l’anomalie.

Le prisonnier \(i\) commence par ouvrir la boîte \(i\). Supposons qu’elle contienne le numéro \(j\). Il ouvre alors la boîte \(j\), puis la boîte portant le numéro qu’il vient d’y trouver, et ainsi de suite.

Autrement dit, chaque prisonnier suit le cycle de la permutation auquel appartient son numéro.

Si ce cycle a une longueur d’au plus 50, il trouvera forcément son numéro avant d’avoir ouvert 50 boîtes. Tous les prisonniers réussissent donc exactement lorsque la permutation ne contient aucun cycle de longueur supérieure à 50.

Pour une permutation aléatoire de 100 éléments, la probabilité d’avoir un cycle de longueur \(k\) vaut \(1/k\). Pour \(k>50\), deux tels cycles ne peuvent pas coexister, donc ces événements sont disjoints. La probabilité d’échec est alors

\[ \frac1{51}+\frac1{52}+\cdots+\frac1{100}. \]
La probabilité de réussite vaut donc

\[ 1-\sum_{k=51}^{100}\frac1k \approx 0{,}3118. \]
soit environ 31,18 %.

C’est gigantesque par rapport à une stratégie où chacun ouvrirait 50 boîtes au hasard indépendamment : la chance que les 100 réussissent serait alors de l’ordre de \(2^{-100}\), pratiquement nulle.

Le prisonnier placé tout au fond voit les 99 chapeaux devant lui. Ils ont convenu que :

• il dira « noir » s’il voit un nombre pair de chapeaux noirs ;
• il dira « blanc » s’il en voit un nombre impair.

Cette première réponse code donc un seul bit : la parité. Elle n’est pas nécessairement la vraie couleur du premier prisonnier, qui n’a qu’une chance sur deux d’être sauvé.

Le prisonnier suivant connaît maintenant la parité annoncée et voit les 98 chapeaux devant lui. Il peut donc déterminer si son propre chapeau doit être noir ou blanc pour que la parité totale soit celle annoncée.

Puis le suivant connaît la parité initiale, les réponses exactes déjà données et les chapeaux encore visibles. Il déduit à son tour sa propre couleur. Le raisonnement continue ainsi jusqu’au dernier.

99 prisonniers sont sauvés avec certitude, et le premier à parler a en plus une chance sur deux d’être sauvé.

On montre par récurrence que, s’il y a exactement \(n\) malades, ils quittent tous le monastère le \(n^ ext{e}\) soir.

Cas \(n=1\). Le seul malade ne voit aucun malade. Après l’annonce de l’abbé, il comprend donc immédiatement que le malade est lui-même et part le lundi soir.

Passage de \(n\) à \(n+1\). Avec \(n+1\) malades, chacun en voit exactement \(n\) et se dit : « Si je suis sain, alors ces \(n\) moines partiront le \(n^ ext{e}\) soir. » Lorsqu’ils constatent que personne n’est parti ce soir-là, chacun comprend qu’il est lui aussi malade. Ils partent donc tous le soir suivant.

Il suffit maintenant de compter : Le départ collectif a lieu le 11^e soir.

Il y avait donc 11 moines malades.

Pose à n’importe lequel des deux dieux :

« Si je demandais à l’autre dieu quelle porte mène à la liberté, quelle porte me montrerait-il ? »

Le dieu véridique rapporte fidèlement le mensonge de l’autre : il indique la mauvaise porte. Le dieu menteur ment sur la réponse correcte qu’aurait donnée le dieu véridique : lui aussi indique la mauvaise porte.

Il suffit donc de prendre l’autre porte.

Appelons \(Q(P)\) la question : « Si je te demandais si \(P\) est vraie, me répondrais-tu oui ? »

Pour Vérité comme pour Mensonge, \(Q(P)\) reçoit la réponse oui si et seulement si \(P\) est vraie. On peut donc interroger de façon fiable tout dieu dont on sait qu’il n’est pas Hasard.

Question 1 à A : \(Q(\text{« B est Hasard »})\).

• Si A répond oui, alors C n’est pas Hasard.
• Si A répond non, alors B n’est pas Hasard.

Appelons \(X\) ce dieu désormais certain de ne pas être Hasard : \(X=C\) après « oui », et \(X=B\) après « non ».

Question 2 à X : \(Q(\text{« A est Hasard »})\).

• oui ⟹ A est Hasard ;
• non ⟹ A n’est pas Hasard.

Question 3.
• Si A est Hasard, demande à \(X\) : \(Q(\text{« Tu es Vérité »})\). On identifie alors \(X\), puis le troisième dieu par élimination.
• Si A n’est pas Hasard, le dieu restant hors de A et \(X\) est Hasard. Demande alors à \(X\) : \(Q(\text{« A est Vérité »})\). Cette dernière réponse distingue A et \(X\) entre Vérité et Mensonge.

Les trois identités sont ainsi déterminées en trois questions au maximum.