J'ai une nouvelle idée (basée sur l'algorithme de tri par insertion ).

Avant de partir pour les grottes on procède comme suit:
On commence par séparer les jeunes qui vont aller à la grotte pour la première fois.
2 jeunes se mettent un derrière l'autre en file indienne, puis 1 par 1 chaque Oompalas, en commençant par les jeunes pas encore placés descendent la file déjà présente et s'inserent entre 2 Oompalas dont les yeux ne sont pas de la même couleur.
S'il ne trouve pas de séparation, il se met à la fin.
De cette façon tous ceux d'une couleur sont devant et tous ceux de l'autre couleur sont derrière.
Personne ne peux en déduire la couleur de ses yeux.

Pendant le trajet, les jeunes se conforment aux indications des adultes matures.
A la queue du premier goupe se trouve des adultes qui connaissent le chemin de leur grotte et à la tête du second groupe aussi.
Ils se séparent naturellement le moment venu.

Le dernier adulte à s'insérer crée une partition. Il sait lui-même où il doit aller.
Tous ceux devant lui ont la même couleur d'yeux et tous ceux derrière aussi.
Autour de lui il y a 2 adultes qui savent donc où aller (comme l'an dernier): celui de devant lui mène le groupe de tous ceux qui sont devant et celui de derrière mène le groupe de tous ceux qui sont derrière.

Non car j'ai bien pris la peine de préciser qu'ils sont en file indienne.
Ceux qui sont de part et d'autre de celui qui s'insère savent qu'ils n'ont pas la même couleur d'yeux mais aucun ne voit les yeux de l'autre.
Celui de derrière voit les yeux de celui qui s'insère mais ne peut en déduire la propre couleur de ses yeux.
De même s'il va à la fin, les 2 premiers ne peuvent pas savoir si c'est parce qu'il est comme eux ou parce qu'il est différent.

Elpafio :

Bravo Titou.

Ce qui est génial avec ce problème, c'est qu'il existe également une solution s'il y a plusieurs couleurs d'yeux (des rouges, des jaunes, des violets, etc) et autant de grottes que de couleurs.
On peut donc généraliser.

Klim.

Je pense que j'avais trouvé un algorithme qui marche mais tellement plus compliqué.

Je suis bluffé par l'élégance et la simplicité de cette solution.

J'en rajoute un peu pour faire mon malin

La théorie des graphes longtemps méprisée en France met souvent en valeur ce type de raisonnements super bluffant .

Ici la simplicité n'est qu'apparente , j'ai cherché pendant deux jours avant de trouver la solution un peu par hasard .

Vasimolo

Pourtant c'est aussi joli que ta solution, Titou...

Ok, je vais le faire... C'est là : http://www.prise2tete.fr/forum/viewtopic.php?id=10814

Mais Bravo Golgot ! Car si tu penses avoir la solution, c'est que tu l'as forcément !