David Madore's WebLog: Le problème des chapeaux de couleur

Une petite addition à la liste que j'avais faite naguère (+1), dans le genre plus proche de ces problèmes-là (en fait, il s'agit d'une variation sur ce que j'appelais l'archi-classique problème des amazones qui tuent leurs maris quand elles savent qu'ils sont infidèles ; il est aussi apparenté au paradoxe de l'examen surprise) :

Le cruel Docteur No a capturé seize mathématiciens. Il les installe autour d'une table et met sur la tête de trois d'entre eux un chapeau blanc, cinq d'entre eux un chapeau rouge, et huit d'entre eux un chapeau noir. Puis il leur tient le discours suivant (rigoureusement exact) : Messieurs, vous êtes tous de parfaits logiciens, et vous savez que je ne vous dirai que la vérité. J'ai placé sur la tête de chacun d'entre vous un chapeau, soit blanc, soit rouge, soit noir. Chacun de vous peut voir la couleur des chapeaux des quinze autres mathématiciens, mais pas du sien. Votre but sera de déduire la couleur de votre chapeau. Pour cela, nous allons procéder en plusieurs tours : à chaque tour, vous écrirez secrètement dans une enveloppe la couleur que vous aurez déduite de votre chapeau, si vous le pouvez, sinon vous laisserez l'enveloppe vide — puis nous dévoilerons le contenu de chaque enveloppe et nous procéderons à un nouveau tour (et ainsi de suite). Vous n'aurez aucun autre moyen de communication. Si une enveloppe contient une mention incorrecte, je vous ferai tous mourir dans d'atroces souffrances (mais cela ne se produira pas car, en tant que parfaits logiciens, vous n'écririez qu'une couleur dont vous êtes logiquement certains). Si trop de tours passent sans que vous ayez tous déduit la couleur de votre chapeau, je vous mettrai aussi à mort (mais nous savons tous que vous écrirez une couleur dès qu'il est logiquement possible de la déduire). Bien, nous allons commencer. Puis, sentant bien que le problème est impossible, le Docteur No ajoute, comme indication : Toutes les couleurs de chapeaux sont représentées (i.e., au moins l'un d'entre vous a un chapeau de chacune des trois couleurs possibles). Comme vous pouvez d'ailleurs le voir. Que va-t-il se passer ?

Le nœud de ce problème existe sous un nombre infini de variantes (par exemple celle-ci), je l'ai souvent appelé le « problème des amazones » parce que j'ai dû le lire d'abord sous cette forme-là[#], mais il faut faire beaucoup de contorsions pour y mettre toutes les hypothèses nécessaires (que je crois avoir correctement réunies). Ici j'ai ajouté quelques petites subtilités pour rendre la chose plus amusante.

(Si on n'a jamais rencontré ce problème, on peut s'échauffer en réfléchissant à ce qui se passe s'il n'y a qu'un seul mathématicien, puis deux, puis trois, quatre, cinq, tous ayant un chapeau blanc, et l'indication du Docteur No est : au moins l'un de vous a un chapeau blanc. Chaque mathématicien supplémentaire apporte un niveau de profondeur supplémentaire dans le raisonnement, au sens où chacun raisonnera sur les raisonnements de tous les autres.)

Bref, que va-t-il se passer ? Réponse :

Le « paradoxe » avec ce problème, c'est que le Docteur No donne comme indication quelque chose qui est manifestement visible de tous les mathématiciens (tous voient bien qu'il y a un chapeau de chaque couleur, et même, puisqu'il y a trois chapeaux blancs, tous voient bien que tous le voient bien, donc tout le monde savait déjà que l'indication du Docteur No était correcte : elle n'apporte en elle-même aucune information nouvelle à qui que ce soit), mais elle est pourtant indispensable à une quelconque déduction (sans l'indication, aucun mathématicien ne peut jamais déduire quoi que ce soit). L'explication, c'est que si tous les mathématiciens savent que l'information donnée par le Docteur No était correcte, le fait qu'il la prononce apporte une information nouvelle, c'est que maintenant non seulement tout le monde le sait, mais tout le monde sait que tout le monde le sait, et tout le monde sait ça, et ainsi de suite. C'est ce qui rend la déduction possible.

En fait, si on veut faire une analyse vraiment rigoureuse du problème, le cadre est assez complexe : a priori, il s'agit de calcul propositionnel modal, avec 16 modalités correspondant à le mathématicien nº1 sait que jusqu'à le mathématicien nº16 sait que (heureusement vérifiant le système standard S5 de la logique modale). Et les modèles d'une telle chose sont, en vérité, assez compliqués. Par exemple, si on veut décrire l'ensemble de toutes les configurations possibles, ce n'est pas très aisé : rien qu'avec un mathématicien, il y a douze « états » possibles (le mathématicien a un chapeau blanc et ne sait rien sur la couleur de celui-ci, il a un chapeau blanc et il sait qu'il n'est pas rouge, il a un chapeau blanc et il sait qu'il n'est pas noir, il a un chapeau blanc et il sait qu'il est blanc, et de façon analogue pour chacune des deux autres couleurs) ; pour deux mathématiciens, il faut tenir compte non seulement de la couleur du chapeau de chacun, et de ce qu'il en sait, mais aussi de ce que l'autre sait qu'il en sait, et ainsi de suite jusqu'à un niveau arbitrairement élevé, ce qui fait une infinité de possibilités — il y a certainement des façons intelligentes de définir des états « utiles » en nombre fini, mais je n'ai pas les idées complètement claires.

On peut aussi penser au problème sous un angle vaguement algorithmique, si un mathématicien voit p autres mathématiciens ayant un chapeau blanc, q avec un chapeau rouge, et r avec un chapeau noir, en fonction de ce qui a été annoncé aux tours précédents, que doit-il mettre dans son enveloppe ? Ce qui est assez étonnant, c'est que si les mathématiciens avaient l'occasion de se concerter entre eux (avant de recevoir les chapeaux, évidemment, mais après avoir reçu l'indication il y a au moins un chapeau de chaque couleur, ou pour être exactement identique à ce que j'ai écrit, il y a au moins deux chapeaux de chaque couleur), leur stratégie serait de toute façon la même : cette concertation ne sert à rien. (Elle est utile, en revanche, s'ils ne reçoivent aucune indication : dans ce cas, ils peuvent décider de prendre le risque de mourir si le Docteur No a cité une couleur pour laquelle il n'a placé aucun chapeau.)

[#] Sans doute dans une des colonnes mathématiques de l'âge d'or de Scientific American : Mathematical Games de Martin Gardner, Metamagical Themas de Douglas Hofstadter ou bien Mathematical Recreations d'Ian Stewart.