Énigme

Jma : Student2 demande comment faire, je donne la solution. Je ne vois pas ce qui te chagrine là dedans...

Student2 : Personnellement j'ai lu la solution de cette énigme dans un numéro de pour la science. Je ne l'ai pas trouvée par moi même et je ne suis donc pas sûr du chemin à emprunter pour retomber sur la solution que j'ai donnée. Voici une idée de cheminement, peut-être pas la bonne.

On note $a_i$ la valeur du chapeau du $i$-ième prisonnier. Plutôt que de chercher à trouver la valeur de leur chapeau les prisonniers peuvent essayer de trouver la valeur $\sum a_i$. Ce problème est équivalent puisque le prisonnier $j$ connait $\sum_{i\neq j} a_i$ et donc s'il connait $\sum a_i$ il en déduit automatiquement $a_j$ (et vice versa). L'avantage de ce changement de perspectives est que tous les prisonniers cherchent alors à deviner la même quantité. La deuxième idée est alors de se dire que, puisque les $a_i$ sont entre $0$ et $N-1$, il suffit de connaitre $\sum a_i \mod N$ et $\sum_{i\neq j} a_i$ pour en déduire $\sum a_i$ quelque soit l'entier $j$. Il est impossible pour les prisonniers de connaître $\sum a_i \mod N$ mais puisqu'il n'y a que $N$ possibilités et que les prisonniers sont au nombre de $N$ il suffit que chaque prisonnier teste une valeur différente pour $\sum a_i \mod N$ : le prisonnier $0$ fait comme si $\sum a_i = 0 \mod N$, le $1$ fait comme si $\sum a_i =1 \mod N$ etc.

On voit alors facilement qu'un seul des prisonniers trouvera la bonne quantité et ce prisonnier est justement le prisonnier numéro $\sum a_i \mod N$.

Edit : l'idée de passer à $\Z/N\Z$ et de prendre la somme des valeurs des chapeaux apparaît dans une autre énigme de prisonniers et de chapeaux.