petite explication pour l'énigme des nains :
un nain ne peuvent voir que le chapeau des nains devant lui.
en donnant à chaque couleur une valeur numérique, il peut ainsi faire la somme des chapeaux qu'il voit.
Rouge = 1, vert = 2 bleu = 3 jaune = 4 et noir = 0.
Notre nain voit 7 chapeaux devant lui : Jaune, Bleu, Bleu, Noir, Vert, Jaune, Rouge.
Il calcule donc la somme 4 + 3 + 3 + 0 + 2 + 4 + 1 = 17.
17 = 2 Modulo 5 (c'est à dire que le reste de la division euclidienne de 17 par 5 vaut 2 -> 17 = 5 * 3 + 2)
Ne connaissant pas la couleur de son chapeau il a 1 chance sur 5 de dire la bonne couleur (quelque soit la couleur qu'il annonce)
2 étant le nombre pour la couleur vert, il annonce vert bien fort pour que tous les nains devant lui l'entendent.
Son sort nous importe peu, passons au nain devant lui :
Ce nain (avant dernier) sait que la somme de leurs chapeaux est congrue à 2 modulo 5 (Cf définition de la congruence). Il calcule donc la somme des chapeaux qu'il voit : Jaune, Bleu, Bleu, Noir, Vert, Jaune -> 4 + 3 + 3 + 0 + 2 + 4 = 16
16 = 1 modulo 5 donc sachant que le nain précédent a dit vert (équivalent à 2), son chapeau est de la couleur correspondant au chiffre 1 (2 - 1 = 1 et 1 = 1 modulo 5) soit Rouge. Il le crie suffisamment fort pour que tous les nains devant lui l'entendent et il est sauvé.
le nouveau nain (avant avant dernier) sait que la somme de leurs chapeaux est congrue à 1 modulo 5 et que le nain précédent a un chapeau vert. Il calcule donc la somme des chapeaux qu'il voit : Jaune, Bleu, Bleu, Noir, Vert -> 4 + 3 + 3 + 0 + 2 = 12 plus le chapeau rouge de son prédécesseur on a 12 + 1 = 13
13 = 3 modulo 5 donc sachant que le premier nain a dit Vert (équivalent à 2), son chapeau est de la couleur correspondant au chiffre 4 (2 - 3 = -1 et -1 = 4 modulo 5) soit Jaune. Il le crie suffisamment fort pour que tous les nains devant lui l'entendent et il est sauvé.
le nouveau nain (le 4ème) sait que la somme de leurs chapeaux est congrue à 1 modulo 5 et que les nains précédents ont un chapeau vert et un chapeau Jaune. Il calcule donc la somme des chapeaux qu'il voit : Jaune, Bleu, Bleu, Noir -> 4 + 3 + 3 + 0 = 10 plus le chapeau rouge et jaune de ses prédécesseurs, on a 10 + 1 + 4 = 15
15 = 0 modulo 5 donc sachant que le premier nain a dit Vert (équivalent à 2), son chapeau est de la couleur correspondant au chiffre 2 (2 - 0 = 2 et 2 = 2 modulo 5) soit Vert. Il le crie suffisamment fort pour que tous les nains devant lui l'entendent et il est sauvé.
etc...
Si ça marche pour 8 nains avec 5 couleurs, ça marche pour autant de nains que vous souhaitez avec autant de couleurs que vous souhaitez.
