Égnime de trie

[Étienne9]

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.

[Étienne9]

Personne n'y arrive ?

[Étienne9]

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.

[Étienne9]

Vous abandonnez ou quoi ?

[Boltzmann_Solver]

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.

[Étienne9]

Bravo ! C'était la solution qu'il fallait trouver !