Je n'arrive pas à démontrer grand chose, ce problème n'est vraiment pas simple.

Sinon, je vais réfléchir à cette dernière question.

Si je comprends bien cette dernière question, le mieux que j'arrive à faire, c'est à terminer dans la case 1 (lorsqu'on place le 7 initial dans la case 8, ou 9, ou 15). Je suppose donc que ce doit être impossible, mais je n'ai pas trouvé l'argument permettant de le justifier.

Je donne ici la réponse à la 1ère partie de la question. Celle ci reste ouverte pour l'instant !


Chaque entier qui numérote une case se décompose en nombres premiers. Avec les jetons J2 à J7, si tous les nombres premiers de la décomposition d'un entier sont > 7, on peut dire que c'est un nombre premier relativement aux jetons, car une telle case ne peut être occupée qu'une seule fois lorsqu'elle peut être atteinte. Vis à vis des jetons, la suite des entiers est donc cyclique modulo le PPCM des J2 à J7, soit 4 * 3 * 5 * 7 = 420. Et d'une façon générale, le cycle est le PPCM (J2....Jn).

On peut modéliser, pour toute case occupée la 1ère fois, l'état des possibilités de mouvements pour chaque jeton.

Exemple lorsque la case 24 est atteinte :

J2 -----> ( fonction: peut atteindre) J3
J3 -----> (rien)
J4------>J3
J5------>
J6----->J3
J7------>

Rien qu'à la lecture de ce diagramme, on devine que c'est J3 qui occupe la case 24 puisque J3 peut être atteint par 4 et 3, et que J3 n'est sûrement pas resté en case 12.

On remarque que ce diagramme est indépendant de la position des jetons.

Ce diagramme nous indique aussi que c'est à J2 à bouger (c'est le prioritaire) et que quand il aura bougé, il remplacera J3 en destination. Si l'on exclut les nouvelles possibilités offertes par les cases suivantes, voici comment évolue le diagramme :

J2---->
J3---->
J4---->J2
J5---->
J6---->J2
J7---->

puis :

J2---->
J3---->
J4---->
J5---->
J6---->J4
J7---->

puis :

J2---->
J3---->
J4---->
J5---->
J6---->
J7---->

fin.

L'évolution est prévisible sans tenir aucun compte de la position réelle des jetons.

Heureusement,les nouvelles cases occupées par les jetons chassés viennent renouveller le diagramme.

Si l'on prend comme référence de case le PPCM J2...Jn, si elle est atteinte, il est évident que 2 diagrammes identiques à 2 multiples de PPCM se répéteront en boucle indéfiniment. Les types de diagrammes possibles sont en quantité finie, puisque le nombre d'images est limité par le nombre de jetons lui même. On a donc, théoriquement, la possibilté de savoir si un mouvement sera perpétuel ou non en allant voir l'évolution sur un grand nombre de cases.

D'après les données founies par le programme d' Ebichu, on se rend compte que, non seulement on n'atteint pas même la fin du cycle, mais que le rapport entre la case bloquante et la fin de cycle diminue lorsque le nombre de jetons augmente (de l'ordre de 10 millionnième pour n = 32).

@nodgim : jolie démonstration C'est drôlement bien vu.

@Vasimolo : je ne pense pas. Regarde le cas classique, les jetons 234567 initialement posés sur les cases 234567. Le jeton n°4 se retrouve sur la case n°11, mais il n'est pas bloqué pour autant (il ira sur la case n°12 quatre coups plus tard).

Je savais bien que j'avais perdu le fil

Vasimolo