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 : Au premier tour, toutes les
enveloppes sont vides. Au deuxième tour, tous les (trois)
mathématiciens ayant un chapeau blanc indiquent que c'est le cas (et
les autres enveloppes sont vides) ; notons que ceci se serait produit
un tour plus tard si le Docteur No n'avait pas dit comme vous
pouvez le voir
. Au troisième tour, rien de nouveau (les trois au
chapeau blanc n'ont évidemment rien de nouveau à dire, les treize
autres rendent enveloppe vide). Au quatrième tour, les (cinq)
mathématiciens au chapeau rouge annoncent correctement la couleur.
Enfin, au cinquième tour, ce sont les (huit) mathématiciens restants
qui disent avec raison avoir un chapeau noir.
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.