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
Il existe une stratégie qui permet de sauver au moins 99 logiciens, et parfois 100 !

Évidemment, le premier à parler n’a aucune information, et quoiqu’il dise, il a une chance sur deux de trouver la couleur de son chapeau. On ne peut donc pas faire mieux que la stratégie décrite ci-dessous.

Le premier à parler compte le nombre de chapeaux noirs parmi les 99 chapeaux qu’il voit. Si ce nombre est pair, il dit « blanc », et si ce nombre est impair, il dit « noir ». Le deuxième à parler compte ensuite le nombre de chapeaux noirs devant lui, et peut comparer la parité de ce nombre avec la ce qu’à dit celui dernière lui. Si c’est la même parité, il sait qu’il a un chapeau blanc, et sinon qu’il a un chapeau noir. Puis le troisième déduit à partir des deux réponses précédentes la couleur de son chapeau, et ainsi de suite.

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
La réponse est oui !

On commence par associer à chaque disposition de chapeaux un nombre entre \({0}\) et \({1}\) en base binaire

\(\displaystyle x = 0, a_1 a_2 \ldots a_n a_{n+1} \ldots , \)

où \({a_k = 0}\) si le k-ème chapeau est blanc, et \({a_k = 1}\) sinon. On introduit la relation d’équivalence \({\sim}\) sur \({\mathbb{R}}\) tel que

\(\displaystyle x \sim y \quad {\Longleftrightarrow} \quad x – y \quad \text{a un nombre fini de chiffres en base binaire}. \)

Autrement dit, \({x \sim y}\) si leur écriture en base binaire termine par la même infinité de chiffres. Il est facile de vérifier que \({\sim}\) est une relation d’équivalence. On considère ensuite l’ensemble des classes d’équivalence \({\mathbb{R} / \sim }\). Pour chaque classe d’équivalence \({C \in \mathbb{R} / \sim }\), les logiciens se mettent d’accord sur un représentant \({x_C \in C}\) (ce qui est possible grâce à l’axiome du choix).

Lors du jeu, puisque chaque logicien voit tous les chapeaux devant lui, chacun sait dans quelle classe d’équivalence \({C}\) appartient leur configuration \({x}\). Les logiciens n’ont plus qu’à réciter les chiffres en base binaire de \({x_C}\) : la \({k}\)-ème personne dira « blanc » si le \({k}\)-ème chiffre en case binaire de \({x_C}\) est un \({0}\), et « noir » sinon.

Puisque \({x \sim x_C}\), il existe un rang \({n \in N}\) tel que tous les chiffres de \({x}\) après le \({n}\)-ème sont les mêmes que ceux de \({x_C}\). À partir de ce rang, tous les logiciens seront sauvés.

Lien pour marque-pages : Permaliens.

Laisser un commentaire

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