Forum de mathématiques - Bibm@th.net

Glozi

Invité

Des petites fourmis sur une horloge

Bonsoir,
Je suis tombé sur cette petite énigme assez sympa je trouve.
Prenez une horloge à aiguille, enlevez les aiguilles et prenez 3 fourmis, la première rouge, la deuxième bleue, la dernière violette. Les fourmis sont au départ sur 3 heures adjacentes, disons que la rouge est sur 12h, la bleue sur 1h et la violette sur 2h, dans cet ordre.
Vous pouvez ensuite bouger les fourmis une par une : vous pouvez faire avancer une fourmi de 5h ou la faire reculer de 5h. Une fourmi a le droit de sauter par dessus une ou plusieurs autres fourmi, mais elle n'a pas le droit d’atterrir sur une heure où il y a déjà une fourmi.

Le but c'est de bouger les fourmis en suivant ces règles, et d'arriver à mettre la rouge sur 2h, la bleue sur 1h et la violette sur 12h (en gros inverser la rouge et la violette de départ).

▼indice

Si vous n'y arrivez pas, il y a sûrement une raison, mais laquelle et pourquoi ?

Bonne soirée

Boody

Membre

Inscription : 31-03-2014

Messages : 183

Re : Des petites fourmis sur une horloge

Bonsoir Forum,

Merci pour cette énigme très sympa.

Le nerf de la guerre a l'air d'être le 7h (because 12 - 5 = 7 = 2 + 5) : on bloque souvent dessus (edit : voir toujours ?).

Ex.
(Je renomme les fourmis en 0, 1 et 2)
On arrive facilement à inverser 0 et 2 mais en se retrouvant avec 1 en 7 et donc blocage.

Je continue à chercher...(edit : ou pas ?)

Dernière modification par Boody (17-04-2023 23:41:47)

Glozi

Invité

Re : Des petites fourmis sur une horloge

Bonjour,
Petit message à l'intention de celles et ceux qui ont un peu cherché l'énigme (Boody c'est pour toi !)

▼secret

Merci de t'être intéressé à l'énigme, je vois dans tes edits que tu commences à douter de la faisabilité de ce casse-tête (et tu as raison).
La tâche semble impossible, mais comment savoir si c'est vraiment le cas ?
Je donne un petit (gros) indice juste après si tu en ressens le besoin.

▼ indice si vous avez deja un peu cherché

Peut-être qu'en réordonnant de manière astucieuse les chiffres sur l'horloge on y verra plus clair ?

Bonne journée

Pharcie75

Invité

Re : Des petites fourmis sur une horloge

Bonjour,

Je dois me tromper, parce que je démontre c'est impossible :
les fourmis peuvent se déplacer selon les arêtes d'un graphe circulaire non orienté dont les sommets sont :
12 5 10 3 8 1 6 11 4 9 2 7

On peut renuméroter les sommets en la suite (0,1,2,3,4,5,6,7,8,9,10,11), et on voit que le problème est exactement équivalent au problème qui consiste à faire se déplacer les fourmis d'un sommet n au sommet n+1 ou n-1, et à placer au départ la fourmi A sur le sommet 0, la fourmi B sur le sommet 5, et la fourmi C sur le sommet 10. Le but est alors d'échanger les positions des fourmis C et A.

À partir des positions initiales A0,B5,C10, il est très facile d'atteindre les positions A0,B1,C2 en déplaçant les fourmis sans les croiser.
De même, à partir des positions finales A10,B5,C0, il est très facile d'atteindre les positions A2, B1, C0.
Il s'agit donc simplement de faire passer les fourmis de la position A0 B1 C2 à la position C0 B1 A2. 
Comme il est interdit de croiser les fourmis sur un sommet du graphe, les seules permutations qu'on puisse faire sont des compositions de permutations qui consistent à faire faire le tour du cadran à la fourmi de numéro supérieur, ou à celle de numéro inférieur dans l'autre sens.
Si on classe les fourmis dans l'ordre croissant du numéro de leur sommet, on n'a donc que le droit de transformer ABC en CAB ou en BCA.
On a deux permutations de signature paire, ce qui ne permet que de faire des permutations de signature paire. Or la permutation qu'on cherche à faire dans le problème est la permutation ABC -> CBA, qui est une permutation de signature impaire.
J'en conclus que c'est impossible, et c'est certainement tout faux, puisque je suppose que le problème a une solution...

Glozi

Invité

Re : Des petites fourmis sur une horloge

Bravo Pharcie75 ! Tu as trouvé il n'y a effectivement pas de solution :) (aie confiance en ton raisonnement !)
J'avais posté cette énigme pour que les gens tournent un peu en rond (c'est le cas de le dire) avant d'essayer de démontrer que ce n'est pas possible !
L'argument de réordonner les chiffres de l'horloge est très joli je trouve.
Mathématiquement parlant, si on a une horloge avec $n$ numéros (ici $n=12$) alors la même énigme s'adapte si le nombre de pas $p$ des fourmis est premier avec $n$ (de sorte que dans notre cas $p=5$ est bien premier avec $n=12$).
Bravo :)

Pharcie75

Invité

Re : Des petites fourmis sur une horloge

Ah d'accord, merci !
Je n'avais pas lu tes indications, mais j'avais supposé que puisque tu en donnais, cela signifiait qu'il y a une solution au problème :-)