Des étudiants en logique au nombre de $N$ sont soumis à un test. On leur explique qu’on va les aligner les uns derrière les autres, tous tournés vers la droite. On posera sur leur tête un chapeau rouge ou bleu tiré au hasard. L’étudiant le plus à gauche pourra voir tous les chapeaux sauf le sien; celui placé devant lui pourra voir tous les chapeaux sauf le sien et celui de l’étudiant placé derrière lui. Plus généralement, l’étudiant placé en position $k,$ à partir de la gauche, pourra voir tous les chapeaux des étudiants $k + 1, k + 2,$ etc. jusqu’au dernier le plus à droite, mais aucun autre. On interrogera chaque étudiant sur la couleur du chapeau qu’il a sur la tête et on leur distribuera ensuite autant d’ordinateurs portables qu’ils auront donné de bonnes réponses. On précise encore qu’avant de se mettre en rang les étudiants sont autorisés à discuter entre eux pour convenir d’une stratégie de réponses, mais qu’une fois alignés les chapeaux seront placés au hasard et qu’ils ne pourront plus avoir d’échanges. Dernière précision : on interrogera les étudiants à voie haute et ils répondront, à voie haute, sur ce que chacun croit être la couleur de son chapeau, en commençant par l’étudiant le plus à gauche et en terminant par celui le plus à droite.
L’étudiant Alonso dit: « nous pouvons être certains de gagner un ordinateur chacun, sauf peut-être l’un de nous ». Il semble impossible que les $N$ étudiants puissent gagner de manière certaine $N-1$ ordinateurs et peut-être $N!$ Pourtant, Alonso est un très bon étudiant qui ne se trompe jamais. Quelle est l’idée d’Alonso ?
Solution
La solution se fonde sur la transmission d’étudiant en étudiant de l’information sur la parité (pair ou impair) du nombre de chapeaux rouges placés à partir de lui (en comptant son chapeau). Plus précisément:
– L’étudiant 1 (le plus à gauche) indique rouge pour son chapeau si le nombre de chapeaux rouges qu’il voit est pair et il indique bleu sinon. Il a une chance sur deux de gagner.
– L’étudiant 2, s’il voit devant lui un nombre de chapeaux rouges qui à la même parité que le nombre de chapeaux rouges qu’a vu l’étudiant 1 (ce qu’il sait puisqu’il a entendu la réponse de l’étudiant 1), est certain d’avoir sur la tête un chapeau bleu, et sinon, d’avoir sur la tête un chapeau rouge. Il répond conformément à sa déduction et ne peut pas se tromper.
– L’étudiant 3, qui connaît la parité du nombre de chapeaux rouges parmi les chapeaux 2, 3, …, $k$), et qui sait si l’étudiant 2 à un chapeau rouge ou pas (car il a entendu sa réponse), connaît donc la parité du nombre de chapeaux rouges des étudiants des rangs 3 à $N.$ Comme il voit aussi tous les chapeaux des rangs 4 à $N,$ il en déduit la couleur de son chapeau.
– De proche en proche, tous les étudiants du deuxième jusqu’au dernier donnent la bonne couleur pour leur chapeau. Au total, tous, sauf peut-être le premier, devinent correctement la couleur de leur chapeau. Le premier a seulement une chance sur deux d’avoir bon.
En résumé:
– Une fois sur deux, les étudiants emporteront $N$ ordinateurs,
– Et une fois sur deux, ils en emporteront $N-1.$
