Histoire
Pour son 12e et dernier travail, Eurysthée tenta de se débarrasser d'Hercule en lui demandant de ramener Cerbère, le molosse à trois têtes qui gardait la porte des enfers. Hercule dut en premier lieu naviguer sur le Styx, afin d'atteindre le trône d'Hadès, gardé par Cerbère. Hadès était plutôt conciliant et il proposa à Hercule de partir avec Cerbère, à condition qu'il puisse le maîtriser à mains nues.
Contrairement à ce qui est souvent raconté, Hercule n'usa pas de violence, et ne frappa pas Cerbère avec une énorme massue. Il usa d'un stratagème plus subtil, révélé par Athéna elle-même. Elle lui expliqua que, sur les trois têtes de Cerbère, deux d'entre elles étaient férues de mathématiques, et la troisième n'avait que peu de discernement :
« Voici des maillons de cinq couleurs différentes : Rouge, Vert, Bleu, et Jaune et Noir. Nous dirons R, V, B, J et N dans la suite. Fabrique un collier pour la tête sans jugeote de Cerbère, de telle façon que n'importe quelle séquence de trois couleurs soit présente sous forme de maillons consécutifs dans ce collier. Dis à Cerbère que c'est un cadeau et passe-lui le collier. Puis annonce à Cerbère que tu as fabriqué pour lui un collier qui contient toutes les séquences de trois couleurs parmi cinq, et que ce collier est le plus petit ayant cette propriété. Ses têtes malignes ne pourront pas s'empêcher de vérifier. Une des têtes surdouées va compter et recompter les maillons pour voir si tu t'es trompé ou non, pendant que l'autre essaiera de trouver un collier plus court ayant la même propriété. La troisième tête devrait se contenter de sourire béatement. Emmène Cerbère pendant qu'il est occupé à réfléchir, il ne te fera pas de difficulté. Mais attention, si tu t'es trompé, qu'il manque une séquence, ou que le collier n'est pas le plus court possible, Cerbère le découvrira et te dévorera sans pitié.»
Défi
Pour aider Hercule, donnez-lui la liste des maillons permettant de réaliser un
tel collier. Le collier sera décrit par une simple
chaîne de caractères contenant les initiales des couleurs : RJJBRJB...
Testez votre code
Imaginons qu'il n'y ait que 2 couleurs, le bleu et le rouge, et que l'on construise un collier qui contienne toutes les séquences de trois couleurs. Le collier devrait donc contenir les séquences :RRR, RRB, RBR, RBB, BRR, BRB, BBR, BBB.
Bien sûr les mettre bout à bout permettrait de réaliser un collier qui comporterait toutes ces séquences, mais
ce ne serait pas le plus court (il aurait pour longueur 24).
Le collier suivant, par contre :
contient bien toutes les séquences de trois couleurs. Il contient seulement huit maillons, et on ne peut pas faire plus court.
Pour résoudre le défi avec simplement deux couleurs et des triplets, il suffirait
de répondre en donnant la séquence des maillons : RBRBBBRR