[Un peu de maths?] L’énigme des chapeaux

Hey ! Je suis de retour !

Désolée pour cette absence d’une petite semaine, je n’étais pas tout à fait en vacances en train de bronzer sur une plage de sable fin, mais plutôt en énorme stress de fin d’études et de présentation de mon projet final. J’ai du coup été forcée de mettre le blog sur pause quelques jours pour me consacrer à cette lourde tâche, mais désormais c’est derrière moi, alors je vais avoir bien plus de temps à te consacrer (youpi !).

Et pour fêter ce début de vacances et la fin de tout ce stress, j’ai décidé de reprendre les [Un peu de maths ?] et d’enfin lever le mystère qui planait sur cette fameuse énigme des chapeaux ! Si tu as entendu parler de mon concours, tu sais déjà de quoi je parle, et sinon je t’offre un petit récapitulatif.

La donnée est la suivante :

Dix personnes sont assises en rond dans une pièce toute vide. Elles ont quelques minutes pour élaborer une stratégie, suite à quoi elles sont forcées de se taire et on met à chacune d’elle un chapeau sur la tête, soit noir, soit blanc. Personne ne connaît le nombre exact de chapeaux noirs et de chapeaux blancs, mais chacun voit la couleur du chapeau des neuf autres personnes (mais personne ne voit son propre chapeau). L’un après l’autre, chacun doit dire « Noir » ou « Blanc » : les personnes qui ont deviné correctement la couleur de leur propre chapeau sont libérées, celles qui se trompent sont exécutées sur-le-champ (oui pardon, les contextes mathématiques, va savoir pourquoi, ça implique toujours des morts). Ma question est la suivante : quelle est la meilleure stratégie à adopter (avant de recevoir les chapeaux) pour sauver à coup sûr le plus de personnes possibles ?

Si j’autorisais toutes sortes de réponses farfelues pour le concours, ici on passe aux choses sérieuses et on va résoudre le problème de façon mathématique. Il n’est donc pas question de faire des signes discrets au voisin ou de contourner les règles : toute l’information qu’on peut transmettre doit être contenue dans le fait de dire « noir » ou « blanc ».

Ce problème est classique dans le monde des maths, et on le trouve d’ailleurs certainement trop facile, puisqu’on s’est amusé à le généraliser à n couleurs de chapeaux et m personnes (où n et m sont absolument n’importe quel chiffre de ton choix)(et quand je dis « on », c’est un « on » tout à fait général, j’ai personnellement d’autres passe-temps dans la vie). Et puisque c’était encore trop simple, il est possible de généraliser encore ce problème en ayant une infinité de couleurs de chapeaux et une infinité de gens. Mais pour aujourd’hui on va faire simple et on va s’attaquer au cas de base, hein ?

La stratégie la plus intuitive, c’est de convenir que le premier dit la couleur du voisin, du coup le voisin répète ce qu’il a entendu et est sauvé, et le troisième dit à son tour la couleur de son voisin, qui répète, etc. Mais le problème, c’est que cette stratégie ne sauve à coup sûr que la moitié des gens. Comprends par là que ça peut en sauver plus, si celui qui se dévoue pour dire la couleur de son voisin a de la chance, mais dans le pire des cas on n’a qu’une personne sur deux qui a la bonne réponse. Et une personne sur deux, c’est pas top-top, on est d’accord. Il doit donc y avoir une meilleure stratégie, qui permettrait à plus de gens d’être sauvés à coup sûr !

Avant que tu ne t’enflammes, je suis obligée de te prévenir tout de suite : on ne pourra pas garantir que les dix seront sauvés. Bah oui, le premier n’a aucune information au moment de prendre la parole, donc pour lui ce sera forcément une question de chance. Par contre, je prétends qu’il existe une stratégie qui permette de sauver TOUS les autres à coup sûr.

Qu’est-ce que ça veut dire ? ça veut dire qu’à partir de l’information du premier gaillard, qui dira donc simplement « noir » ou « blanc », tout le monde sera capable d’en déduire la couleur de son propre chapeau. Je sais pas toi, moi je trouve ça extrêmement cool.

Mais comment ça marche alors ? Si on avait plus de deux couleurs de chapeaux, on devrait partir dans du jargon mathématique à base de modulo et de reste de division, et c’est justement la raison pour laquelle j’hésite à t’expliquer ce cas-là. Mais avec deux couleurs c’est beaucoup plus simple, les seules notions que tu dois connaître c’est pair et impair. C’est le moment d’illustrer la situation, ça va être plus simple à expliquer.

Je te présente donc nos dix bonshommes, avec leurs chapeaux noirs et blancs. J’ai dit dans l’énoncé qu’ils peuvent élaborer une stratégie à l’avance : ils vont donc convenir d’un code. Le premier à prendre la parole va compter le nombre de chapeaux noirs qu’il voit : si c’est un nombre pair, il dira « Noir », si c’est un nombre impair, il dira « Blanc ». Tout le monde est au courant de ce code (on aurait pu le fixer autrement hein, en se basant sur les chapeaux blancs, en inversant le code pair/impair, mais peu importe).

Avec mon exemple, voilà ce qui va se passer : numéro 1 va regarder autour de lui : comme il voit les chapeaux de tout le monde sauf le sien, il compte 5 chapeaux noirs. Selon le code préétabli, il va ainsi dire « Blanc« . Malheureusement, dans ce cas, son propre chapeau est noir alors il aura tort, mais il s’est sacrifié pour le bien commun (eh oui, pardon). C’est maintenant au tour de numéro 2, qui sait que numéro 1 a compté un nombre impair de chapeaux noirs. Il va donc regarder autour de lui, et compter le nombre de chapeaux noirs qu’il voit sans prendre en compte le chapeau de numéro 1, puisque lui-même ne le voyait pas. Il regarde donc les chapeaux de numéro 3 jusqu’à numéro 10, et il compte cinq chapeaux noirs. Il en conclut donc que lui-même a un chapeau blanc, et peut ainsi dire « Blanc », ce qui le sauve. De la même manière, numéro 3 va compter les chapeaux noirs sans regarder celui de numéro 1, et n’en voyant que quatre, il saura que le sien doit être noir pour arriver à un nombre impair.

En gros, chacun va être capable de déduire la couleur de son propre chapeau, sur la base de la première information !

Et j’en profite pour claquer la bise au Tanuki, la seule qui a trouvé cette stratégie dans le cadre du concours ! Malheureusement le but n’était pas de récompenser la personne la plus douée en maths, mais tu as toutes mes félicitations parce qu’elle est pas simple, cette énigme !

Je m’arrête là pour cette fois, si l’explication était claire et que ça t’intéresserait de voir comment on s’y prendrait avec trois couleurs, fais-le moi savoir et je tenterai de l’expliquer dans le prochain rendez-vous matheux.

Oh et j’en profite aussi pour te dire que je viens d’ouvrir ma page facebook ! Rapport au fait que j’ai enfin du temps, tout ça. Alors je vais prendre mes marques petit à petit, mais je t’invite à y passer si ça t’intéresse, je vais tenter de publier du contenu régulièrement.

C’est tout pour moi, et je te laisse avec le générique de Chapi Chapo, parce que j’étais obligée (il est presque un peu glauque en fait, non ?).