Comments on Le problème des chapeaux de couleur

More Doctor No problems described at <URL: http://spikedmath.com/puzzle-002.html > .

Agreed, this problem seems well-known. I've heared it told most often with a hundred cheating men in the village: every woman knows about every other man whether they cheat their wife; if a wife learns that his husband is cheating on her, he must kill her husband during the night, of which everyone else will learn in the morning; and a mysterious stranger announces that at least one of the husbands cheats. A less common variant is when a train passes through a tunnel, after which the inspector announces in the carriage that those passengers who have got soot on their face from the tunnel can get off at any stop and wash it.

By the way, why don't you update the older entries to link to the newer related ones? In this case, update entry d.2006-11-20.1390 to link to this post.

Also, I'm missing the “tuer avec des tortures particulièrement raffinées” from this problem. Did you not include that because it's something only you would use in the description, but Doctor No himself would not say?

Il y a quelques chapitres dans l'ouvrage suivant : http://www.cambridge.org/gb/knowledge/isbn/item1162310/ (Introduction to Non-Classical Logic)

Est-ce que tu connais un bouquin intéressant sur les logiques modales ?

@Abc: « Toutes les couleurs sont représentées. »

@Mazoit : Précisons que « Comme vous pouvez d'ailleurs le voir. » implique qu'il y a au moins 2 chapeaux de chaque couleur, car s'il n'y avait qu'un seul chapeau blanc, celui qui le porte ne pourrait pas « le voir » (= voir qu'il y a au moins un chapeau de chaque sorte).

Or s'il n'y avait que 2 chapeaux blancs, les deux porteurs de chapeaux blancs n'en verront qu'un et diront dès le premier tour qu'ils le portent.

Mais en réalité, comme il y a trois chapeaux blancs, les enveloppes restent vides au premier tour et tous en déduisent qu'il y au moins trois chapeaux blancs. Au deuxième tour, tous ceux qui ne voient que deux chapeaux blancs répondent donc qu'ils ont un chapeau blanc.

Bref, c'est ce que tu disais avec un tour d'avance (comme précisé dans la réponse de David), formulé un peu différemment pour augmenter les chances de compréhension des « non logiciens » :-)

Par ailleurs, je n'aime pas trop la formulation « Au moins l'un d'entre vous a un chapeau de chacune des trois couleurs possibles. » Quelqu'un en voit-il une meilleure ?

Disons que les numéros 1,2 et 3 sont blancs, les cinq suivants noirs et les autres rouges.

Au premier tour, personne ne peut rien savoir. J'imagine que c'est assez clair pourquoi.
Au deuxième tour, n°1 peut se dire :
"Supposons que je sois en noir.
Alors n°2 ne verrait qu'un autre chapeau blanc (celui de n°3). N°2 saurait nécessairement qu'il est en blanc!
En effet, supposons que n°2 suppose qu'il est en noir (sic!). Alors dans ce cas, n°3 ne verrait aucun blanc et déduirait donc qu'il est blanc. Mais il n'a pas pu le faire! Donc n°2 ne peut pas supposer qu'il est noir (idem pour rouge).
Id est, il saurait qu'il est blanc (ie, au premier tour!).
Mais il ne l'a pas su.
Donc je ne suis pas noir (idem pour rouge).
Donc je suis blanc."
n°2 et n°3 font le même raisonnement à la fin du premier tour.

Au deuxième tour, ils déduisent donc qu'ils sont en blanc.

Dans le genre, Tarence Tao a fait deux billets sur le sujet que je trouve très intéressants:
- http://terrytao.wordpress.com/2011/04/07/the-blue-eyed-islanders-puzzle-repost/
- http://terrytao.wordpress.com/2011/05/19/epistemic-logic-temporal-epistemic-logic-and-the-blue-eyed-islander-puzzle-lower-bound/

Il faut raisonner par récurrence sur le nombre de chapeau d'une couleur donnée.

1. Supposons qu'il y a un seul chapeau blanc.
Il y a quelqu'un qui ne voit aucun chapeau blanc. Or, comme on lui a dit qu'il y en avait au moins 1, il déduit que c'est lui qui le porte. Il répond donc au premier tour.

2. Supposons qu'il y a deux chapeaux blancs.
Mettons nous à la place d'un porteur de chapeau blanc (monsieur x) qui ne voit qu'un seul chapeau blanc.
Si monsieur x ne porte pas de chapeau blanc, c'est qu'il n'y a qu'un seul chapeau blanc au total. Par récurrence, l'unique porteur de chapeau blanc peut (et va) répondre au premier tour.
S'il n'y a pas eu de réponse au premier tour, c'est qu'il y a un autre chapeau blanc. Et donc monsieur x déduit que c'est lui qui le porte. Il répond au second tour.

3. Le cas général est le suivant. Un porteur de chapeau blanc voit n chapeaux blanc. Si à la fin du tour n, les n porteurs n'ont pas deviné la couleur de leur chapeau, c'est qu'il y a au moins n+1 chapeaux blancs. Le porteur devine donc la couleur de son chapeau.

Salut,

Est-ce que tu peux détailler les étapes du raisonnement pour que des non logiciens comprennent qui "observe et comprend quoi" à chaque tour de vote, pourquoi ce sont les blancs qui commencent à comprendre, pourquoi il y a un tour blanc ensuite, etc.

Merci