Archivé

Ce sujet est désormais archivé et ne peut plus recevoir de nouvelles réponses.

Messages recommandés

Bonjour,

Une énigme pas évidente pour vous (les informaticiens veuillez laisser les autres réfléchir s'il vous plaît).

Il y a deux types de nain, des nains avec des chapeaux bleus et des nains avec des chapeaux rouges.

On ne sait pas combien il y a de chaque, les nains ne connaissent pas la couleur de leur chapeau et ne peuvent pas parler ni faire de gestes.

Les nains savent faire UNIQUEMENT deux choses :

- Regarder la couleur des chapeaux des autres.

- Se déplacer.

Le but : trier les nains quelque soit le nombre qui a des chapeaux rouges et le nombre qui a des chapeaux bleus.

Partager ce message


Lien à poster
Partager sur d’autres sites

Indice:

Soit la propriété P(n) définie par "Le groupe qui contient n naim(s) est trié".

On en déduit que P(0), P(1) et surtout que (P2) est vraie.

Partager ce message


Lien à poster
Partager sur d’autres sites

Exemple d'algo.

Le groupe de nain se place à la queue et on leur donne la consigne suivante. Il se place successivement et en ligne à la limite entre le rouge et le bleu.

Soit 0, le bleu et 1 le rouge. Celui en gras est le nain placé au rang i=k.

i=0 : 0|

i=1 : 0|1

i=2 : 00|1

i=3 : 000|1

i=4 : 000|11

etc...

Enfin, les algos de tri existant sont très nombreux.

Partager ce message


Lien à poster
Partager sur d’autres sites