Chapeaux rouges et bleus

Énoncé

100 nains sont en file indienne. Chaque nain porte un chapeau, de couleur rouge ou bleue, mais ne le voit pas. Il peut cependant voir les chapeaux de tous les nains devant lui dans la file. Le défi est le suivant : chacun leur tour, et en partant du dernier nain, les nains vont devoir deviner la couleur de leur chapeau et la dire à voie haute. Ils peuvent, avant la pose des chapeaux, se concerter sur une stratégie. Quelle stratégie peuvent-ils adopter pour qu'au moins 99 d'entre eux devinent correctement la couleur de leur chapeau ?

Solution

Puisqu'il faut qu'au moins 99 des nains devinent correctement la couleur de leurs chapeaux, on devine facilement que c'est le premier nain à s'exprimer qui peut se tromper. Ce nain est cependant crucial : c'est lui qui va donner suffisamment d'information pour que tous les autres nains puissent deviner la couleur de leur chapeau. La stratégie est la suivante : le premier nain va dire « bleu » si le nombre de chapeaux bleus parmi les 99 nains devant lui est pair, « rouge » sinon. Entendant cela, le deuxième nain va à son tour compter le nombre de chapeaux bleus parmi les 98 nains devant lui. Si celui-ci a la même parité que pour le premier nain, alors le nombre de chapeaux bleus n'a pas varié et le chapeau du deuxième nain est rouge. Sinon, puisque le nombre de chapeaux bleus a varié, c'est que le chapeau du deuxième nain est bleu. Le deuxième nain peut donc deviner correctement la couleur de son chapeau. Puis, ayant entendu l'information donnée par le premier nain et la couleur du chapeau du deuxième nain, le troisième nain va pouvoir connaître la parité du nombre de chapeaux bleus parmi lui et les 97 nains devant lui : il s'agira de celle indiquée par le premier nain si le deuxième nain avait un chapeau rouge, et son inverse sinon. Il va donc à son tour pouvoir deviner la couleur de son chapeau. De façon générale, le n-ème nain va pouvoir deviner la couleur de son chapeau. Et ainsi de suite.