L'énigme Des Nains

[wapiti]

10 nains ont été capturés par un ogre qui leur propose le challenge suivant :

Demain, vous vous alignerez à la queue leu leu, chacun ne pouvant voir que les nains qui sont devant lui. Je disposerai ensuite des chapeaux noir ou blanc sur la tête de chacun de vous. Puis, le dernier de la file devra deviner la couleur de son chapeau. S'il devine juste, je le laisse partir, sinon, je le mange. Puis le suivant fait de même, même traitement, et ainsi de suite jusqu'au premier de la file.

Question : Sachant que les nains ont la nuit pour élaborer une stratégie, quel est le nombre minimum de nains qui peuvent être sauvés ?

NB: on supposera que tous les nains suivront la stratégie fixée au préalable.

[Coldstar]

Précision: les nains auront-ils connaissance du nombre de chapeaux noirs et blancs?

EDIT: non, forcément, sinon c'est trop facile.

[Coldstar]

Je propose: cinq peuvent être sauvés assurément.

Je ne suis pas sûr du résultat. Je donnerai mon raisonnement plus tard pour ceux qui veulent chercher.

[wapiti]

Vu ton chiffre de 5, j'imagine ton raisonnement, mais on peut faire beaucoup mieux.

[Coldstar]

Oui, jusqu'à 9 avec une astuce… Le problème, c'est que j'ai des idées d'astuces, mais qu'elles sont un peu capilotractées.

Par contre, sauver les dix à coup sûr me paraît impossible.

[Invité Arcani]

Oui, jusqu'à 9 avec une astuce… Le problème, c'est que j'ai des idées d'astuces, mais qu'elles sont un peu capilotractées.

Par contre, sauver les dix à coup sûr me paraît impossible.

<{POST_SNAPBACK}>

Aucun.

[Sous-Commandant Marco]

J'ai failli péter un câble mais la réponse est 9. De façon plus générale, on peut sauver n-1 nains. Seul le dernier nain dans la file a une chance sur deux d'être mangé.

Voici le raisonnement. Le dernier nain de la file compte le nombre de chapeaux blancs sur les neuf nains qui sont devant lui. Si ce nombre est pair, il répond "blanc", s'il est impair, il répond "noir".

A partir de là, la réponse que doit donner chaque nain est déterminée comme suit:

-mémoriser la réponse R donnée par le nain précédent,

-compter le nombre de chapeaux blancs sur les nains devant soi-même. Notons N ce nombre,

-si N est pair et R est "blanc" ou bien si N est impair et R est "noir" alors répondre "noir", dans les autres cas, répondre "blanc".

Pour les neufs nains qui restent, cette réponse est nécessairement la bonne et chaque nain est donc sauvé. On doit pouvoir le démontrer rigoureusement mathématiquement (par récurrence) mais je vais juste vous donner une idée de la démonstration.

Si la réponse donnée par le premier nain est "blanc", il y a un nombre pair de chapeaux blancs sur les neufs nains qui restent. Si le neuvième nain voit aussi un nombre pair de chapeaux blancs devant lui, c'est donc que son propre chapeau est noir. S'il voit un nombre impair de chapeaux blancs, c'est donc que son propre chapeau est blanc. En fait, dans ce cas, la réponse "noir" signifie aussi: "il reste un nombre pair de chapeaux blancs devant moi" tandis que la réponse "blanc" signifie "il reste un nombre impair de chapeaux blancs devant moi".

Inversement, si la réponse donnée par le premier nain est "noir", alors la réponse "blanc" signifie "il reste un nombre pair de chapeaux blancs devant moi" et "noir" signifie "il reste un nombre impair de chapeaux blancs devant moi".

Bon, ben, j'ai bien mérité un petit Ardisson, moi…

[wapiti]

(*EDIT* presque) Bien joué Sous-Commandant Marco

Mais il me semble que ton algorithme ne marche pas bien que tu ais l'idée.

[Sous-Commandant Marco]

(*EDIT* presque) Bien joué Sous-Commandant Marco

Mais il me semble que ton algorithme ne marche pas bien que tu ais l'idée.

<{POST_SNAPBACK}>

C'est fort possible en effet, pourtant j'ai passé un bon bout de temps à hésiter entre "blanc" et "noir"! Il ne marche plus à partir du nain 8! Damned.

L'idée est bonne mais l'algorithme est faux. Il faut le modifier comme suit.

Le dernier nain compte les chapeaux blancs devant lui. Si ce nombre est impair, il dit "blanc", s'il est pair, il dit "noir".

Les nains suivants doivent compter le nombre S de réponses "blanc" données par tous les nains précédents (là était mon erreur), compter le nombre N de chapeaux blancs devant eux, puis calculer la somme S+N. Si cette somme est impaire, il doivent répondre "blanc". Si elle est paire, ils répondent "noir".

Pour me faire pardonner de ma bévue, je propose une autre énigme, très connue mais sait-on jamais.

Je vous donne une grille carrée de 8 x 8 carreaux et 32 dominos. Les dominos couvrent exactement deux carreaux adjacents de la grille. Vous êtes d'accord qu'il y a un très grand nombre de manières de couvrir complètement la grille avec les dominos. Bon maintenant, je scie un carreau situé en un coin de la grille. Je scie aussi le carreau qui lui est exactement opposé en diagonale. La grille ne compte donc plus que 62 carreaux. Et je vous enlève un domino.

Question: combien y a t-il de manières différentes de couvrir complètement la grille avec les 31 dominos qui restent?

[Coldstar]

Pour me faire pardonner de ma bévue, je propose une autre énigme, très connue mais sait-on jamais.

Je vous donne une grille carrée de 8 x 8 carreaux et 32 dominos. Les dominos couvrent exactement deux carreaux adjacents de la grille. Vous êtes d'accord qu'il y a un très grand nombre de manières de couvrir complètement la grille avec les dominos. Bon maintenant, je scie un carreau situé en un coin de la grille. Je scie aussi le carreau qui lui est exactement opposé en diagonale. La grille ne compte donc plus que 62 carreaux. Et je vous enlève un domino.

Question: combien y a t-il de manières différentes de couvrir complètement la grille avec les 31 dominos qui restent?

<{POST_SNAPBACK}>

Je ne sais pas si ce sont les chapeaux blancs et noirs qui t'ont rappelé cette énigme, mais la démonstration de la réponse, que je connais, suggère l'usage d'un jeu où l'on parle aussi en noir et blanc. Je ne me demande même pas si Dilbert saura trouver la réponse, vu son avatar

[wapiti]

Facile avec ton indication Coldstar …