On va supposer que les fourmis portent des dossards et qu'elles échangent leur dossard lorsqu'elles se rencontrent.
Les dossards tournent à vitesse constante et vont donc se retrouver en position initiale simultanément en ayant fait chacun un tour au bout de D (D=1 minute, temps pour faire un tour).
Par contre, ils seront portés par des fourmis vraisemblablement différentes.
Si N fourmis sont présentes dans l'anneau, il y a N! façon de distribuer les dossards aux fourmis, donc au bout d'un temps N! D, on est sur que les dossards seront portés selon une distribution déjà rencontrée.
Donc le mouvement des fourmis est périodique, d'une période inférieure ou égale à N! D.
En pratique, pour N = 3, la période est soit D (toutes les fourmis tournent dans le même sens), soit 3 D (2 dans un sens, 1 dans l'autres).
Après quelques heures de creusage :
Puisque les fourmis ne se croisent pas, elles conservent le même ordre dans le tube, simplement décalé de P positions (entre 0 à N-1 positions) lorsque les dossards ont fait un tour.
En faisant faire T tours aux dossards, on aura décalé les fourmis de TP positions. En choissant T = N/PGCD (P, N), on aura décalé de PN/PGCD(P,N)=PPCM(P,N) donc les fourmis sont revenues à leur position initiale.
Donc la période est au maximim N D, elle pourra être un diviseur de N.
Exemple :
4 fourmis :
toutes dans le même sens : période D
2 dans un sens, 2 dans l'autre : période 2 D
3 dans un sens, 1 dans l'autre : période 4 D.
Rem : c'est en fait un problème de permutation, la période est égale à l'"ordre" de cette permutation.
Accueil
