Les chapeaux

Si les chapeaux sont un peu passés de mode, les problèmes des chapeaux restent des grands classiques.

Les chapeaux

Dans la prison des logiciens, on propose le jeu suivant à 100 prisonniers. On dispose les 100 prisonniers en file indienne, de sorte que chaque logicien peut voir les logiciens devant lui, mais pas ceux derrière lui. On place un chapeau noir ou blanc sur la tête de chacun d’entre eux, puis on demande tour à tour aux logiciens de deviner la couleur de leur chapeau. On commence par demander à celui de derrière (celui qui voit 99 chapeaux), puis on remonte pour finir avec celui de devant (celui qui n’en voit aucun). Chaque logicien entend toutes les réponses précédentes.

Si un logicien trouve la couleur de son chapeau correctement, il est libéré. S’il ne trouve pas, il est condamné à faire des mathématiques appliquées pour le restant de ses jours.

Les logiciens ont le droit de ce concerter avant le jeu et d’établir une stratégie. Quelle stratégie permet de minimiser le nombre de matheux appliqués ?

Avant de donner la réponse à ce problème, en voici une version différente.

Les chapeaux (bis)

On propose maintenant un autre jeu à 100 autres prisonniers. Ils sont maintenant dans une salle, de sorte que chacun voit les chapeaux des autres, mais pas le sien. On demande ensuite à un logicien au hasard de deviner la couleur de son chapeau, et tout le monde entend sa réponse. Puis on sépare tous les logiciens, et on demande aux 99 autres logiciens de deviner la couleur de leur chapeau.

Quelle stratégie permet de sauver le maximum de logiciens ?

Cliquez ici pour voir la solution

Pour les plus sportifs, vous pouvez essayer la version suivante, avec une infinité de logiciens et de chapeaux.

Les chapeaux, cas indénombrable (***)

Dans la prison de Hilbert, il y a un nombre infini (dénombrable) de logiciens. On décide de les faire jouer au jeu des chapeaux en ligne. De nouveau, chacun voit tous les chapeaux devant lui (en nombre infini maintenant), et doit trouver la couleur du sien.

Les logiciens peuvent-ils trouver une stratégie avant le jeu qui permet de les sauver tous, sauf éventuellement un nombre fini d’entre eux ?

Pour finir, voici une dernière version, ma préférée.

Encore une infinité de chapeaux

Dans cette même prison, on propose un autre jeu. On met tous les logiciens dans une salle (toujours une infinité dénombrable), et chacun voit tous les autres chapeaux sauf le sien. On sépare ensuite les logiciens, et chacun doit trouver la couleur de son chapeau.

Les logiciens peuvent-ils trouver une stratégie avant le jeu qui permet de les sauver tous, sauf éventuellement un nombre fini d’entre eux ?

J’aime beaucoup cette dernière version, puisque cette fois-ci, aucune information n’est échangée oralement, et que malgré le fait que la couleur du chapeau d’un logicien est indépendante du choix des autres chapeaux, ils peuvent se sauver globalement.

Cliquez ici pour voir la solution

Lien pour marque-pages : Permaliens.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *