Casse-têtes d'induction - Induction puzzles

Fait partie d'une série sur
énigmes
Les types Devinant cribler Situation Logique Dissection Induction Grille logique Auto-référence Mécanique Combinaison Construction Démêlage Serrure Allez les problèmes Pliant Coller Carrelage Tour Glissement Jeu d'échecs Labyrinthe  ( Labyrinthe logique ) Mot et nombre Mots croisés Sudoku Jeux vidéo d'énigmes Labyrinthes Métapuzzles
Les sujets Casse-tête Dilemme Illusion d'optique Problèmes d'emballage Paradoxe Résolution de problème Chasse aux puzzles Syllogisme Sortir des sentiers battus
Listes énigmes impossibles Labyrinthe jeux vidéo Types de puzzles Nikoli Jeux vidéo d'énigmes Sujets de casse-tête
v t e

Les énigmes d'induction sont des énigmes logiques , qui sont des exemples de raisonnement multi-agents , où la solution évolue avec le principe d' induction .

Le scénario d'un puzzle implique toujours plusieurs joueurs avec la même capacité de raisonnement, qui passent par les mêmes étapes de raisonnement. Selon le principe d'induction, une solution au cas le plus simple rend évidente la solution du prochain cas compliqué. Une fois le cas le plus simple du puzzle d'induction résolu, tout le puzzle est résolu par la suite.

Les caractéristiques typiques de ces puzzles incluent tout puzzle dans lequel chaque participant possède une information donnée sur tous les autres participants mais pas sur eux-mêmes. De plus, généralement, une sorte d'indice est donné pour suggérer que les participants peuvent se fier à l'intelligence de l'autre - ils sont capables de théorie de l'esprit .

L'énigme boueuse des enfants est l'énigme d'induction qui apparaît le plus fréquemment dans la littérature scientifique sur la logique épistémique . En février 2020, 437 résultats sur Google Scholar mentionnaient le casse-tête boueux des enfants. Le puzzle des enfants boueux est une variante des puzzles bien connus des hommes sages ou des femmes/maris infidèles.

Les puzzles de chapeaux sont des variantes de puzzles à induction qui remontent à 1961. Dans de nombreuses variantes, les puzzles de chapeaux sont décrits dans le contexte des prisonniers. Dans d'autres cas, les puzzles de chapeaux sont décrits dans le contexte des sages.

Puzzle enfants boueux

La description

Il y a un ensemble d'enfants attentifs. Ils pensent parfaitement logiquement. Les enfants considèrent qu'il est possible d'avoir le visage boueux. Aucun des enfants ne peut déterminer lui-même l'état de son propre visage. Mais, chaque enfant connaît l'état du visage de tous les autres enfants. Un gardien dit aux enfants qu'au moins l'un d'entre eux a le visage boueux. Par la suite, le gardien commence à compter et après chaque AVC, chaque enfant boueux a la possibilité de s'avancer.

Solution logique

Supposons qu'il n'y ait que 2 enfants : Alice et Bob. Si seulement Alice est sale, elle s'avancera du premier coup, car elle ne voit pas d'autres visages sales. C'est la même chose pour Bob. Si Alice voit Bob ne pas s'avancer au premier coup, elle doit conclure qu'il voit certainement un autre enfant boueux et qu'ils avanceront simultanément au deuxième coup.

Supposons qu'il n'y ait que 3 enfants : Alice, Bob et Charly. S'il y a moins de 3 enfants boueux, le puzzle évolue comme dans le cas de 2 enfants. Si Charly voit qu'Alice et Bob sont boueux et qu'ils n'avancent pas au deuxième coup, ils avanceront tous ensemble au troisième coup.

Il peut être prouvé que les enfants boueux s'avanceront après les accidents vasculaires cérébraux. ${\style d'affichage X}$${\style d'affichage X}$

Solution de la théorie des jeux

Les énigmes boueuses des enfants peuvent également être résolues en utilisant l' induction en arrière de la théorie des jeux . Le puzzle boueux des enfants peut être représenté comme un jeu de forme étendu d' informations imparfaites . Chaque joueur a deux actions : rester en arrière et avancer. Il y a un mouvement de la nature au début du jeu, qui détermine les enfants avec et sans visage boueux. Les enfants ne communiquent pas comme dans les jeux non coopératifs . Chaque coup est un mouvement simultané des enfants. C'est un jeu séquentiel de durée illimitée. La solution de la théorie des jeux nécessite quelques hypothèses supplémentaires :

1. Tous les enfants sont rationnels et la rationalité de tous les enfants est de notoriété publique . Cela signifie qu'Alice est rationnelle, Alice sait que Bob est rationnel et Alice sait que Bob sait que Charly est rationnel et ainsi de suite et vice versa.
2. Avancer sans avoir le visage boueux entraîne une grosse pénalité.
3. S'avancer avec un visage boueux donne lieu à une récompense.
4. Chaque coup entraîne une pénalité négative mineure, c'est-à-dire un facteur de réduction pour chaque enfant jusqu'à ce que l'un d'entre eux se manifeste. Tout multiple de la peine mineure est toujours un moindre mal que la grande peine.

Si seulement Alice est boueuse, la dernière hypothèse la rend irrationnelle pour elle d'hésiter. Si Alice et Bob sont boueux, Alice sait que la seule raison pour laquelle Bob reste en arrière après le premier coup est l'appréhension de recevoir la lourde pénalité de s'avancer sans un visage boueux. Dans le cas des enfants boueux, recevoir des fois la pénalité mineure est toujours mieux que la grande pénalité. ${\style d'affichage X}$${\style d'affichage X}$

Casse-tête des hommes sages du roi

La description

Le roi appela à sa cour les trois hommes les plus sages du pays pour décider qui deviendrait son nouveau conseiller. Il plaça un chapeau sur chacune de leurs têtes, de sorte que chaque homme sage puisse voir tous les autres chapeaux, mais aucun d'eux ne pourrait voir le sien. Chaque chapeau était blanc ou bleu. Le roi donna sa parole aux sages qu'au moins l'un d'entre eux portait un chapeau bleu ; en d'autres termes, il pourrait y avoir un, deux ou trois chapeaux bleus, mais pas zéro. Le roi a également annoncé que le concours serait équitable pour les trois hommes. Il était également interdit aux sages de se parler. Le roi déclara que celui qui se levait le premier et annonçait correctement la couleur de son propre chapeau deviendrait son nouveau conseiller. Les sages restèrent assis très longtemps avant que l'un d'eux ne se lève et annonce correctement la réponse. Qu'a-t-il dit et comment l'a-t-il résolu?

Solution

The King's Wise Men est l'un des puzzles d'induction les plus simples et l'un des indicateurs les plus clairs de la méthode utilisée.

• Supposons qu'il y ait un chapeau bleu. La personne avec ce chapeau verrait deux chapeaux blancs, et puisque le roi précisait qu'il y avait au moins un chapeau bleu, ce sage connaîtrait immédiatement la couleur de son chapeau. Cependant, les deux autres verraient un chapeau bleu et un chapeau blanc et ne seraient pas en mesure de déduire immédiatement des informations à partir de leurs observations. Par conséquent, ce scénario violerait la spécification du roi selon laquelle le concours serait équitable pour chacun. Il doit donc y avoir au moins deux chapeaux bleus.
• Supposons alors qu'il y ait deux chapeaux bleus. Chaque homme sage avec un chapeau bleu verrait un chapeau bleu et un chapeau blanc. En supposant qu'ils aient déjà réalisé qu'il ne peut y en avoir qu'un (en utilisant le scénario précédent), ils sauraient qu'il doit y avoir au moins deux chapeaux bleus et donc, sauraient immédiatement qu'ils portaient chacun un chapeau bleu. Cependant, l'homme au chapeau blanc verrait deux chapeaux bleus et ne pourrait immédiatement déduire aucune information de ses observations. Ce scénario violerait donc également la spécification selon laquelle le concours serait équitable pour chacun. Il doit donc y avoir trois chapeaux bleus.

Puisqu'il doit y avoir trois chapeaux bleus, le premier homme à comprendre cela se lèvera et dira bleu.

Solution alternative : Cela ne nécessite pas la règle que le concours soit équitable pour chacun. Cela repose plutôt sur le fait qu'ils sont tous des sages et qu'il leur faut un certain temps avant d'arriver à une solution. Il ne peut y avoir que 3 scénarios, un chapeau bleu, deux chapeaux bleus ou 3 chapeaux bleus. S'il n'y avait qu'un seul chapeau bleu, alors le porteur de ce chapeau verrait deux chapeaux blancs, et saura rapidement qu'il doit avoir un chapeau bleu, alors il se lèverait et l'annoncerait tout de suite. Puisque cela ne s'est pas produit, alors il doit y avoir au moins deux chapeaux bleus. S'il y avait deux chapeaux bleus, alors l'un ou l'autre de ceux qui portaient un chapeau bleu regarderait à travers et verrait un chapeau bleu et un chapeau blanc, mais ne connaîtrait pas la couleur de leur propre chapeau. Si le premier porteur du chapeau bleu supposait qu'il avait un chapeau blanc, il saurait que l'autre porteur du chapeau bleu verrait deux chapeaux blancs, et donc le 2ème porteur du chapeau bleu se serait déjà levé et aurait annoncé qu'il portait un chapeau bleu. Ainsi, puisque cela ne s'est pas produit, le premier porteur du chapeau bleu saurait qu'il porte un chapeau bleu, et pourrait se lever et l'annoncer. Étant donné qu'un ou deux chapeaux bleus sont si faciles à résoudre et que personne ne s'est levé rapidement, alors ils doivent tous porter des chapeaux bleus.

Le problème de Joséphine

La description

Dans le royaume de Joséphine, chaque femme doit passer un examen de logique avant d'être autorisée à se marier. Chaque femme mariée connaît la fidélité de chaque homme dans le Royaume, à l' exception de son propre mari, et l'étiquette exige qu'aucune femme ne soit informée de la fidélité de son mari. De plus, un coup de feu tiré dans n'importe quelle maison du Royaume sera entendu dans n'importe quelle autre maison. La reine Joséphine a annoncé qu'au moins un homme infidèle avait été découvert dans le royaume, et que toute femme sachant que son mari était infidèle devait l'abattre à minuit le lendemain du jour où elle avait découvert son infidélité. Comment les épouses ont-elles géré cela?

Solution

Le problème de Joséphine est un autre bon exemple d'un cas général.

• S'il n'y a qu'un seul mari infidèle, alors chaque femme dans le Royaume le sait, à l'exception de sa femme, qui croit que tout le monde est fidèle. Ainsi, dès qu'elle apprend de la reine que les hommes infidèles existent, elle sait que son mari doit être infidèle et lui tire dessus.
• S'il y a 2 maris infidèles, alors leurs deux femmes croient qu'il n'y a qu'un seul mari infidèle (l'autre). Ainsi, ils s'attendront à ce que le cas ci-dessus s'applique et que la femme de l'autre mari l'abatte à minuit le lendemain. Lorsqu'aucun coup de feu n'est entendu, ils se rendent compte que le cas ci-dessus ne s'applique pas , donc il doit y avoir plus d'un mari infidèle et (puisqu'ils savent que tout le monde est fidèle) l'autre doit être leur propre mari.
• S'il y a 3 maris infidèles, chacune de leurs femmes pense qu'il n'y en a que 2, donc elles s'attendront à ce que le cas ci-dessus s'applique et les deux maris seront fusillés le deuxième jour. Lorsqu'elles n'entendront aucun coup de feu, elles se rendront compte que le cas ci-dessus ne s'appliquait pas , donc il doit y avoir plus de 2 maris infidèles et comme avant leur propre mari est le seul candidat à être le suppléant.
• En général, s'il y a n maris infidèles, chacune de leurs épouses croira qu'il y en a n-1 et s'attendra à entendre un coup de feu à minuit le n-1 ème jour. Quand elles ne le font pas, elles savent que leur propre mari était le n ième.

Ce problème est également connu comme le problème des maris infidèles, le problème des femmes infidèles, le problème des enfants boueux. Il est logiquement identique au Blue Eyes Problem .

Ce problème apparaît également comme un problème impliquant des chapeaux noirs et des chapeaux blancs dans le manuel classique de CL Liu « Elements of Discrete Mathematics ».

Alice à la Convention des Logiciens

La description

Lors de la Convention secrète des Logiciens, le Maître Logicien a placé un bracelet sur la tête de chaque participant, de sorte que tout le monde puisse le voir mais pas la personne elle-même. Il y avait beaucoup de couleurs différentes de bande. Les Logiciens s'assirent tous en cercle, et le Maître leur ordonna de sonner une cloche dans la forêt à intervalles réguliers : au moment où un Logicien connaissait la couleur de son propre front, il devait partir à la cloche suivante. Il leur a été demandé de ne pas parler, d'utiliser un miroir ou une caméra ou d'éviter d'utiliser la logique pour déterminer la couleur de leur bande. Au cas où des imposteurs auraient infiltré la convention, toute personne ne partant pas à l'heure serait renvoyée brutalement au bon moment. De même, toute personne essayant de partir tôt serait tenue en place et enlevée au bon moment. Le Maître a rassuré le groupe en déclarant que le puzzle ne serait impossible pour aucun Vrai Logicien présent. Comment ont-ils fait ?

Solution

Alice à la convention des Logiciens est une induction générale plus un saut de logique.

• Saut de logique : chaque couleur doit apparaître au moins deux fois autour du cercle. C'est parce que le Maître a déclaré qu'il ne serait impossible pour aucun Logicien de résoudre le puzzle. Si une couleur n'existait qu'une seule fois autour du cercle, le Logicien qui la portait n'aurait aucun moyen de savoir que la couleur existait même dans le problème, et il lui serait impossible de répondre.
• Chacun des Logiciens peut regarder autour du cercle et compter le nombre de fois qu'il voit chaque couleur. Supposons que vous soyez l'un des Logiciens et que vous ne voyiez une autre couleur qu'une seule fois. Puisque vous savez que chaque couleur doit exister au moins deux fois autour du cercle, la seule explication pour une couleur singleton est qu'il s'agit de la couleur de votre propre bande. Pour la même raison, il ne peut y avoir qu'une seule couleur de ce type et vous partiriez donc à la première cloche.
• De même, tout Logicien qui ne voit une autre couleur qu'une seule fois devrait pouvoir déterminer sa propre couleur et partira avec dignité ou sera jeté comme infiltré. De manière équivalente, toute couleur pour laquelle il n'y a que deux bandes de cette couleur sera éliminée après que la première cloche ait sonné. Par la suite, il doit y avoir au moins trois bandes de n'importe quelle couleur restante.
• Supposons que vous ne voyiez aucune couleur une fois, mais que vous voyiez une couleur deux fois. Si c'étaient les seules bandes de cette couleur, alors ces deux Logiciens auraient dû partir à la première cloche. Comme ils ne l'ont pas fait, cela ne peut être que parce que votre propre groupe est de la même couleur, vous pouvez donc partir à la deuxième cloche.
• Par conséquent, chaque logicien surveillerait jusqu'à ce qu'un groupe d'une couleur donnée qu'il s'attendait à quitter échoue. Alors ils sauraient qu'ils avaient cette couleur et partiraient à la cloche suivante.
• Lorsqu'il ne restait qu'une couleur, cette couleur partait sur la cloche suivante, car ils sauraient qu'ils ne pouvaient pas avoir d'autre couleur (puisqu'il leur serait impossible de connaître leur couleur).

Puzzle de chapeau de base

La description

Un certain nombre de joueurs portent chacun un chapeau, qui peut être de différentes couleurs spécifiées. Les joueurs peuvent voir les couleurs des chapeaux d'au moins certains autres joueurs, mais pas celle du leur. Avec une communication très restreinte ou inexistante, certains joueurs doivent deviner la couleur de leur chapeau. Le problème est de trouver une stratégie pour que les joueurs déterminent les couleurs de leurs chapeaux en fonction des chapeaux qu'ils voient et de ce que font les autres joueurs. Dans certaines versions, ils rivalisent pour être les premiers à deviner correctement ; dans d'autres, ils peuvent élaborer une stratégie à l'avance pour coopérer et maximiser la probabilité de suppositions correctes.

Une variation a reçu une nouvelle publicité à la suite du doctorat de 1998 de Todd Ebert . thèse à l' Université de Californie, Santa Barbara . C'est une question de stratégie sur un jeu coopératif , qui a des liens avec la théorie du codage algébrique .

Trois joueurs sont informés que chacun d'eux recevra soit un chapeau rouge, soit un chapeau bleu. Ils doivent lever la main s'ils voient un chapeau rouge sur un autre joueur alors qu'ils forment un cercle face à face. Le premier à deviner correctement la couleur de son chapeau gagne.

Les trois joueurs lèvent la main. Après que les joueurs se soient vus pendant quelques minutes sans deviner, un joueur annonce "Rouge" et gagne. Comment le gagnant a-t-il fait et quelle est la couleur des chapeaux de chacun ?

Solution

Premièrement, si deux personnes avaient des chapeaux bleus, la main de tout le monde n'aurait pas été levée. Ensuite, si le joueur 1 avait vu un chapeau bleu sur le joueur 2 et un chapeau rouge sur le joueur 3, alors le joueur 1 aurait su immédiatement que son propre chapeau devait être rouge. Ainsi, tout joueur qui voit un chapeau bleu peut deviner immédiatement. Enfin, le gagnant se rend compte que puisque personne ne devine à la fois, il ne doit pas y avoir de chapeaux bleus, donc chaque chapeau doit être rouge.

Dans le cas où chaque joueur doit deviner, mais il est libre de choisir quand deviner, il existe une stratégie coopérative qui permet à chaque joueur de deviner correctement à moins que tous les chapeaux soient de la même couleur. Chaque joueur doit agir comme suit :

1. Comptez les nombres b de chapeaux bleus et r de chapeaux rouges que vous voyez.
2. Attendez b secondes ou r secondes, selon la première éventualité.
3. Si personne n'a encore parlé, devinez que votre chapeau est bleu si vous voyez moins de chapeaux bleus que de chapeaux rouges, ou rouge si vous voyez moins de chapeaux rouges que de chapeaux bleus.
4. Si vous n'avez pas encore parlé, devinez que votre chapeau est de la couleur opposée à celle de l'une des premières personnes à parler.

Supposons qu'il y ait au total B chapeaux bleus et R chapeaux rouges. Il y a trois cas.

Si B = R, alors les joueurs portant des chapeaux bleus voient les chapeaux bleus B−1 et les chapeaux rouges B , alors attendez B −1 secondes puis devinez correctement qu'ils portent un chapeau bleu. De même, les joueurs portant un chapeau rouge attendront R -1 secondes avant de deviner correctement qu'ils portent un chapeau rouge. Ainsi, tous les joueurs font une estimation correcte en même temps.

Si B < R, alors ceux qui portent un chapeau bleu verront B -1 chapeaux bleus et R chapeaux rouges, tandis que ceux qui portent un chapeau rouge verront B chapeaux bleus et R -1 chapeaux rouges. Puisque B −1 < B ≤ R −1, les joueurs portant un chapeau bleu seront les premiers à parler, devinant correctement que leur chapeau est bleu. Les autres joueurs devinent alors correctement que leur chapeau est rouge.

Le cas où R < B est similaire.

Variante à deux chapeaux

La description

Selon l'histoire, quatre prisonniers sont arrêtés pour un crime , mais la prison est pleine et le geôlier n'a nulle part où les mettre. Il finit par trouver la solution de leur donner un casse-tête afin que s'ils réussissent, ils puissent se libérer, mais s'ils échouent, ils sont exécutés.

Le geôlier place trois des hommes en ligne. B fait face au mur, C fait face à B et D fait face à C et B. Le quatrième homme, A, est placé derrière un paravent (ou dans une pièce séparée). Le geôlier donne aux quatre hommes des chapeaux de fête. Il explique qu'il y a deux chapeaux noirs et deux chapeaux blancs, que chaque prisonnier porte un des chapeaux, et que chacun des prisonniers ne voit que les chapeaux devant lui mais ni sur lui ni derrière lui. Le quatrième homme derrière l'écran ne peut voir ou être vu par aucun autre prisonnier. Aucune communication entre les prisonniers n'est autorisée.

Si un prisonnier peut déterminer la couleur de son chapeau sur sa tête avec une certitude à 100% (sans deviner), il doit alors l'annoncer, et les quatre prisonniers sont libérés . Si un prisonnier suggère une réponse incorrecte, les quatre prisonniers sont exécutés. Le casse-tête est de trouver comment les prisonniers peuvent s'échapper.

Solution

Les prisonniers savent qu'il n'y a que deux chapeaux de chaque couleur. Donc, si D observe que B et C ont des chapeaux de la même couleur, D en déduira que son propre chapeau est de la couleur opposée. Cependant, si B et C ont des chapeaux de couleurs différentes, alors D ne peut rien dire. La clé est que le prisonnier C, après avoir laissé un intervalle approprié, et sachant ce que D ferait, peut en déduire que si D ne dit rien, les chapeaux sur B et C doivent être différents ; capable de voir le chapeau de B, il peut déduire sa propre couleur de chapeau.

Comme pour de nombreuses énigmes de ce type, la solution repose sur l'hypothèse que tous les participants sont totalement rationnels et suffisamment intelligents pour faire les déductions appropriées.

Après avoir résolu cette énigme, il est possible d'avoir un aperçu de la nature de la communication en se demandant si le silence significatif du prisonnier D viole la règle « Pas de communication » (étant donné que la communication est généralement définie comme le « transfert d'informations »).

Variante à trois chapeaux

La description

Dans cette variante, il y a 3 prisonniers et 3 chapeaux. Chaque prisonnier se voit attribuer un chapeau au hasard, rouge ou bleu. En tout, il y a trois chapeaux rouges et deux bleus. Chaque personne peut voir les chapeaux de deux autres, mais pas le leur. Sur un signal, ils doivent chacun deviner leur propre couleur de chapeau ou passer. Ils gagnent la libération si au moins une personne a deviné correctement et aucune n'a deviné de manière incorrecte (la réussite n'est ni correcte ni incorrecte).

Ce puzzle n'a pas de stratégie gagnante à 100 %, la question est donc : quelle est la meilleure stratégie ? Quelle stratégie a la plus grande probabilité de gagner ?

Si vous considérez les couleurs des chapeaux comme des bits, ce problème a des applications importantes dans la théorie du codage .

Solution

La solution et la discussion de ce puzzle peuvent être trouvées ici (également une solution au puzzle analogue à 7 chapeaux) et 3 autres variantes sont disponibles sur cette page Logic Puzzles (elles sont appelées Masters of Logic I-IV).

Variante à quatre chapeaux

La description

Dans une variante de ce puzzle, les prisonniers savent qu'il y a 3 chapeaux noirs et 1 chapeau blanc, et les 3 prisonniers peuvent se voir c'est-à-dire que D voit B & C, B voit D & C et C voit D & B. ( A encore ne se voit pas et n'est là que pour porter le dernier chapeau.) Comment peuvent-ils en déduire les couleurs de tous sans communiquer ?

Solution

Il y a deux cas : dans le cas trivial, l'un des trois détenus porte le seul chapeau décoloré. Chacun des deux autres prisonniers peut voir qu'un prisonnier porte le chapeau de couleur différente. Dans le cas non trivial, les trois prisonniers portent des chapeaux de la même couleur, tandis que A porte le chapeau de couleur différente. Après un certain temps, les trois prisonniers devraient être en mesure de déduire que, comme aucun des autres n'était en mesure d'indiquer la couleur de son propre chapeau, A doit porter le chapeau de couleur différente.

Variante à cinq chapeaux

La description

Dans une autre variante, seuls trois prisonniers et cinq chapeaux de couleurs connues (dans cet exemple deux noirs et trois blancs) sont concernés. Les trois prisonniers reçoivent l'ordre de se tenir en ligne droite face à face, avec A devant et C derrière. On leur dit qu'il y aura deux chapeaux noirs et trois chapeaux blancs. Un chapeau est ensuite mis sur la tête de chaque prisonnier ; chaque prisonnier ne peut voir que les chapeaux des personnes devant lui et non le sien. Le premier prisonnier capable d'annoncer correctement la couleur de son chapeau sera libéré. Aucune communication entre les détenus n'est autorisée.

Solution

Supposons que A porte un chapeau noir :

• Si B porte également un chapeau noir, C peut immédiatement dire qu'il porte un chapeau blanc après avoir regardé les deux chapeaux noirs devant lui.
• Si B porte un chapeau blanc, C sera incapable de dire la couleur de son chapeau (car il y a un noir et un blanc). Ainsi, B peut rapidement déduire du chapeau noir de A et de l'absence de réponse de C qu'il (B) porte un chapeau blanc.

Donc, si A porte un chapeau noir, il y aura une réponse assez rapide de B ou C.

Supposons que A porte un chapeau blanc :

• C ne voit pas deux chapeaux noirs, il est donc incapable de dire la couleur de son chapeau.
• B ne voit qu'un chapeau blanc, il ne peut donc rien dire à propos de son chapeau.

Dans ce cas, A, B et C resteraient silencieux pendant un certain temps, jusqu'à ce que A en déduise finalement qu'il doit avoir un chapeau blanc car C et B sont restés silencieux pendant un certain temps.

Comme mentionné, il y a trois chapeaux blancs et deux chapeaux noirs au total, et les trois prisonniers le savent. Dans cette énigme, vous pouvez supposer que les trois prisonniers sont très intelligents et très intelligents. Si C n'a pas pu deviner la couleur de son propre chapeau, c'est parce qu'il a vu soit deux chapeaux blancs, soit un de chaque couleur. S'il avait vu deux chapeaux noirs, il aurait pu en déduire qu'il portait un chapeau blanc.

Variante à dix chapeaux

La description

Dans cette variante, il y a 10 prisonniers et 10 chapeaux. Chaque prisonnier se voit attribuer un chapeau au hasard, rouge ou bleu, mais le numéro de chaque chapeau de couleur n'est pas connu des prisonniers. Les prisonniers seront alignés en file indienne où chacun pourra voir les chapeaux devant lui mais pas derrière. En commençant par le prisonnier en queue de ligne et en avançant, ils doivent chacun, à tour de rôle, prononcer un seul mot qui doit être « rouge » ou « bleu ». Si le mot correspond à la couleur de leur chapeau, ils sont relâchés, sinon, ils sont tués sur le coup. Un gardien sympathique les avertit de ce test une heure à l'avance et leur dit qu'ils peuvent formuler un plan où en suivant les règles énoncées, 9 des 10 prisonniers survivront définitivement, et 1 a 50/50 chances de survie. Quel est le plan pour atteindre l'objectif?

Solution

Les détenus s'accordent à dire que si le premier détenu voit un nombre impair de chapeaux rouges, il dira "rouge". De cette façon, les neuf autres prisonniers connaîtront leur propre couleur de chapeau après la réponse du prisonnier derrière eux.

Variante à dix chapeaux sans audition

La description

Comme avant, il y a 10 prisonniers et 10 chapeaux. Chaque prisonnier se voit attribuer un chapeau au hasard, rouge ou bleu, mais le numéro de chaque chapeau de couleur n'est pas connu des prisonniers. Les prisonniers sont répartis dans la salle de telle sorte qu'ils puissent voir les chapeaux des autres mais pas le leur. Maintenant, ils doivent chacun, simultanément, dire un seul mot qui doit être "rouge" ou "bleu". Si le mot correspond à la couleur de leur chapeau, ils sont libérés, et si suffisamment de prisonniers reprennent leur liberté, ils peuvent secourir les autres. Un gardien sympathique les prévient de cette épreuve une heure à l'avance. S'ils peuvent formuler un plan suivant les règles énoncées, 5 des 10 prisonniers seront définitivement libérés et pourront sauver les autres. Quel est le plan pour atteindre l'objectif?

Solution

Les prisonniers se séparent. Dans une paire (A, B) des prisonniers A dit la couleur qu'il peut voir sur la tête de B, qui dit la couleur opposée qu'il voit sur la tête de A. Ensuite, si les deux portent des chapeaux de la même couleur, A est libéré (et B ne l'est pas), si les couleurs sont différentes, B est libéré (et A ne l'est pas). Au total, 5 détenus répondent correctement et 5 non. Cela suppose que la paire peut communiquer qui est A et qui est B, ce qui peut ne pas être autorisé.

Alternativement, les prisonniers forment deux groupes de 5. Un groupe suppose que le nombre de chapeaux rouges est pair, l'autre suppose qu'il y a un nombre impair de chapeaux rouges. Semblable à la variante avec ouïe, ils peuvent déduire la couleur de leur chapeau de cette hypothèse. Exactement un groupe aura raison, donc 5 prisonniers répondent correctement et 5 non.

A noter que les détenus ne trouvent pas de stratégie garantissant la libération de plus de 5 détenus. En effet, pour un seul détenu, il y a autant de répartitions de couleurs de chapeaux où il dit la bonne réponse qu'il n'y en a où il ne dit pas. Par conséquent, il y a autant de distributions de couleurs de chapeaux où 6 détenus ou plus donnent la bonne réponse qu'il n'y en a où 4 ou moins le font.

Variante de chapeau infiniment dénombrable sans audition

La description

Dans cette variante, un nombre infini de prisonniers, chacun avec un chapeau rouge ou bleu inconnu et attribué au hasard, alignent une seule ligne de file. Chaque prisonnier fait face au début de la ligne, et chaque prisonnier peut voir tous les chapeaux devant lui, et aucun des chapeaux derrière. A partir du début de la ligne, chaque prisonnier doit identifier correctement la couleur de son chapeau ou il est tué sur le coup. Comme auparavant, les détenus ont la possibilité de se rencontrer à l'avance, mais contrairement à avant, une fois en ligne, aucun détenu ne peut entendre ce que les autres détenus disent. La question est de savoir s'il y a un moyen de s'assurer que seulement un nombre fini de prisonniers sont tués ?

Solution

Si l'on accepte l' axiome du choix et suppose que les prisonniers ont chacun la capacité (irréaliste) de mémoriser une quantité infinie d'informations et d'effectuer des calculs avec une complexité de calcul infiniment infinie , la réponse est oui. En fait, même si nous autorisons un nombre incalculable de couleurs différentes pour les chapeaux et un nombre incalculable de prisonniers, l'axiome du choix fournit une solution qui garantit que seul un nombre fini de prisonniers doit mourir à condition que chaque prisonnier puisse voir les chapeaux de tous les autres. prisonnier (pas seulement ceux qui les précèdent dans une ligne), ou du moins que chaque prisonnier peut voir tout sauf un nombre limité des autres chapeaux. La solution pour le cas des deux couleurs est la suivante, et la solution pour le cas des couleurs infinies est essentiellement la même :

Les prisonniers alignés forment une séquence de 0 et de 1, où 0 représente le bleu et 1 représente le rouge. Avant leur mise en ligne, les détenus définissent la relation d'équivalence suivante sur toutes les séquences possibles dans lesquelles ils pourraient être mis : Deux séquences sont équivalentes si elles sont identiques après un nombre fini d'entrées. A partir de cette relation d'équivalence, les détenus obtiennent un ensemble de classes d'équivalence. En supposant l'axiome du choix, il existe un ensemble de séquences représentatives, une pour chaque classe d'équivalence. ( Presque toutes les valeurs spécifique est impossible à calculer, mais l'axiome de choix implique que certains de valeurs existe, donc nous supposons que les prisonniers ont accès à un oracle .)

Lorsqu'ils sont placés dans leur file, chaque prisonnier peut voir tous les chapeaux, sauf un nombre fini, et peut donc voir à quelle classe d'équivalence appartient la séquence réelle de chapeaux. (Cela suppose que chaque prisonnier peut effectuer un nombre infiniment infini de comparaisons pour trouver une correspondance, chaque comparaison de classe nécessitant un nombre infini de comparaisons de chapeaux individuels). Ils procèdent ensuite à deviner la couleur de leur chapeau comme s'ils étaient dans la séquence représentative de la classe d'équivalence appropriée. Parce que la séquence réelle et la séquence représentative sont dans la même classe d'équivalence, leurs entrées sont les mêmes après un nombre fini N de prisonniers. Tous les prisonniers après ces N premiers prisonniers sont sauvés.

Parce que les prisonniers n'ont aucune information sur la couleur de leur propre chapeau et feraient la même estimation quelle que soit la couleur qu'il a, chaque prisonnier a 50% de chances d'être tué. Il peut sembler paradoxal qu'un nombre infini de prisonniers aient chacun une chance égale d'être tués et pourtant il est certain que seul un nombre fini est tué. La solution à ce paradoxe réside dans le fait que la fonction employée pour déterminer la supposition de chaque détenu n'est pas une fonction mesurable .

Pour le voir, considérons le cas de zéro prisonnier tué. Cela se produit si et seulement si la séquence réelle est l'une des séquences représentatives sélectionnées. Si les séquences de 0 et de 1 sont considérées comme des représentations binaires d'un nombre réel compris entre 0 et 1, les séquences représentatives forment un ensemble non mesurable . (Cet ensemble est similaire à un ensemble Vitali , la seule différence étant que les classes d'équivalence sont formées par rapport aux nombres avec des représentations binaires finies plutôt qu'à tous les nombres rationnels.) Par conséquent, aucune probabilité ne peut être attribuée à l'événement de zéro prisonnier tué. L'argument est similaire pour d'autres nombres finis de prisonniers tués, correspondant à un nombre fini de variations de chaque représentant.

Problème de chapeau infiniment infini avec l'audition

La description

Cette variante est la même que la précédente sauf que les prisonniers peuvent entendre les couleurs appelées par les autres prisonniers. La question est, quelle est la stratégie optimale pour les prisonniers afin que le moins d'entre eux meurent dans le pire des cas ?

Solution

Il s'avère que, si l'on permet aux détenus d'entendre les couleurs criées par les autres détenus, il est possible de garantir la vie de tous les détenus sauf le premier, qui meurt avec une probabilité de 50 %.

Pour ce faire, nous définissons la même relation d'équivalence que ci-dessus et sélectionnons à nouveau une séquence représentative de chaque classe d'équivalence. Maintenant, nous étiquetons chaque séquence de chaque classe avec un 0 ou un 1. Premièrement, nous étiquetons la séquence représentative avec un 0. Ensuite, nous étiquetons toute séquence qui diffère de la séquence représentative dans un nombre pair d'endroits avec un 0, et toute séquence qui diffère de la séquence représentative dans un nombre impair de places avec un 1. De cette manière, nous avons étiqueté chaque séquence infinie possible avec un 0 ou un 1 avec la propriété importante que deux séquences qui diffèrent d'un seul chiffre ont des étiquettes opposées.

Maintenant, lorsque le directeur demande à la première personne de dire une couleur, ou dans notre nouvelle interprétation, un 0 ou un 1, il appelle simplement l'étiquette de la séquence qu'il voit. Compte tenu de cette information, tout le monde après lui peut déterminer exactement quelle est sa propre couleur de chapeau. La deuxième personne voit tout sauf le premier chiffre de la séquence que la première personne voit. Ainsi, pour autant qu'il le sache, il y a deux séquences possibles que la première personne aurait pu étiqueter : l'une commençant par un 0 et l'autre commençant par un 1. En raison de notre schéma d'étiquetage, ces deux séquences recevraient des étiquettes opposées, donc basées sur ce que dit la première personne, la deuxième personne peut déterminer laquelle des deux cordes possibles la première personne a vue, et ainsi elle peut déterminer sa propre couleur de chapeau. De même, chaque personne qui suit la ligne connaît chaque chiffre de la séquence sauf celui correspondant à sa propre couleur de chapeau. Il connaît ceux avant lui parce qu'ils ont été appelés, et ceux après lui parce qu'il peut les voir. Avec cette information, il peut utiliser l'étiquette appelée par la première personne pour déterminer sa propre couleur de chapeau. Ainsi, tout le monde sauf la première personne devine toujours correctement.

La version d'Ebert et les codes de Hamming

La description

La version d'Ebert du problème stipule que tous les joueurs qui devinent doivent deviner au même moment prédéterminé, mais que tous les joueurs ne sont pas tenus de deviner. Maintenant, tous les joueurs ne peuvent pas deviner correctement, donc les joueurs gagnent si au moins un joueur devine et tous ceux qui devinent le font correctement. Comment les joueurs peuvent-ils maximiser leurs chances de gagner ?

Solution

Une stratégie pour résoudre cette version du problème du chapeau utilise les codes de Hamming , qui sont couramment utilisés pour détecter et corriger les erreurs dans la transmission des données . La probabilité de gagner sera bien supérieure à 50%, selon le nombre de joueurs dans la configuration puzzle : par exemple, une probabilité de gagner de 87,5% pour 7 joueurs.

Des stratégies similaires peuvent être appliquées à des équipes de N = 2 ^k −1 et obtenir un taux de victoire (2 ^k -1)/2 ^k . Ainsi , la stratégie de code Hamming donne des taux plus élevés de gains pour les plus grandes valeurs de N .

Dans cette version du problème, toute supposition individuelle a 50 % de chances d'avoir raison. Cependant, l'approche du code de Hamming fonctionne en concentrant les suppositions erronées sur certaines distributions de chapeaux. Dans certains cas, tous les joueurs devineront incorrectement ; alors que pour les autres cas, un seul joueur devinera, mais correctement. Alors que la moitié de toutes les suppositions sont encore incorrectes, les joueurs gagnent plus de 50% du temps.

Un exemple simple de ce type de solution à trois joueurs est instructif. A trois joueurs, il y a huit possibilités ; dans deux d'entre eux, tous les joueurs ont le même chapeau de couleur, et dans les six autres, deux joueurs ont une couleur et l'autre joueur a l'autre couleur.

Les joueurs peuvent garantir qu'ils gagnent dans ces derniers cas (75% du temps) avec la stratégie suivante :

1. Tout joueur qui observe deux chapeaux de deux couleurs différentes reste silencieux.
2. Tout joueur qui observe deux chapeaux de la même couleur devine la couleur opposée.

Dans les deux cas où les trois joueurs ont la même couleur de chapeau, ils devineront tous de manière incorrecte. Mais dans les six autres cas, un seul joueur devinera, et à juste titre, que son chapeau est à l'opposé de celui de ses coéquipiers.

Maisons de Sneetchville

La description

Les Sneetches sont des créatures de la célèbre histoire du Dr Seuss "The Sneetches". Il existe deux types de Sneetches, à ventre étoilé et à ventre plat. Tous les Sneetches doivent passer un test de logique pour vivre à Sneetchville, qui compte un nombre limité de maisons et a une loi stricte sur le logement selon laquelle chaque maison ne doit pas contenir plus d'un Sneetch à ventre étoilé et d'un Sneetch à ventre plat. Aucun Sneetch n'est capable de voir son propre ventre, mais peut toujours voir le ventre de tous les autres Sneetch. Pour éviter d'autres conflits entre les Sneetches, il existe une loi qui interdit aux Sneetches de discuter de leur ventre (voir aussi Ne demandez pas, ne dites pas ). Chaque Sneetch ne peut pas sauter une maison jusqu'à ce qu'il soit sûr qu'il ne peut pas y emménager. Si un Sneetch enfreint la loi, il est exécuté. Comment les Sneetches choisissent-ils leur maison ?

Solution

Étant donné que tous les Sneetches sont potentiellement à risque, une solution consiste à ce que tous les Sneetches se rencontrent dans la rue ; le modèle indique des maisons, donc une route, une rue ou à proximité. Là, ils acceptent de s'orienter vers des Sneetches qui se ressemblent et s'éloignent des Sneetches qui se ressemblent; cela évite le besoin de communiquer spécifiquement sur les caractéristiques physiques, c'est-à-dire l'état du ventre. Le mouvement Sneetch commence par un mouvement brownien, mais comme dans la logique du problème des enfants boueux, cela se transforme en agglutination, par exemple, un Sneetch se déplaçant vers deux sneetches similaires étant acceptés ou rejetés par eux, ou vice versa, et finalement un seul espace d'état de deux résultats des groupes, le ventre étoilé et le ventre plat. Un Sneetch du premier groupe va d'abord dans chaque maison, puis un Sneetch du deuxième groupe va dans chaque maison.

Voir également

• Logique épistémique
• Connaissance commune (logique)

Les références