Je ne suis pas sûr de bien comprendre les consignes.

Les consignes impliquent-elles qu'à chaque tour, il n'y a qu'un seul coup possible ? Si oui, peux-tu donner les premiers coups, pour aider à les comprendre ?

Alors OK pour les 1ers coups :

234567 : On cherche si le jeton 2 peut avancer. La case paire la plus proche occupée est la 4: 2 va case 4 et le jeton 4 va en avant, 1ère case libre après le jeton 7: 8
325674. Fin du mouvement. Retour en phase recherche.

On cherche si le jeton 2 peut avancer: la case paire occupée la plus proche devant lui est la 6. Le jeton 2 va en 6 et le jeton 6 va case 9 :
3-52746. fin du mouvement. Retour en phase recherche.

Là encore le jeton 2 a une case paire devant lui occupée en case 8 : 3-5-7264.

Il n'y a donc pas 2 options possibles pour jouer si on respecte les règles. 

@ Golgot: idem, je l'ai fait à la main, 3 fois pour être sûr, et je n'ai pas trouvé pareil que toi.

Pour vous exercer, tentez d'abord avec 5 jetons numérotés de 2 à 6, ça devrait s'arréter assez vite.
Quand vous serez vraiment exercés, si ça vous tente, essayez avec 7 jetons ou plus.

Cela étant dit, je n'ai pas de recette miracle pour prédire le devenir d'un tel algorithme. Cependant, la conclusion peut toujours se mesurer en un temps limité.

Ah OK je vois Golgot. C'est un autre algo qui consiste à boucher les trous le plus possible, c'est à dire à bouger, dès qu'on le peut, le dernier. Intéressant, ça mérite d'être proposé dans un autre fil !

Très joli problème. Pour l'instant, j'ai réalisé un programme pour faire les calculs, car il est très facile de se tromper, et ça peut durer longtemps.

Pour n=7 (jetons de 2 à 7), je trouve que le jeu se termine en 76 étapes, c'est-à-dire que lorsque les jetons sont bloqués, le jeton le plus avancé se trouve en position 76+7=83.

En général, le jeu semble se terminer juste avant un nombre avec beaucoup de diviseurs.

Si tu confirmes le résultat, je peux poster le nombre d'étapes pour d'autres valeurs de n. Après, il restera à analyser le problème mathématiquement...

Pardon, Golgot, je n'avais lu qu'en diagonale tes résultats sans aller au bout, en fait c'est bon !

Bravo pour ta persévérance !

Je ne suis pas sûr d'avoir compris le mouvement des pièces

Avec 5 pièces 2,3,4,5,6 , les mouvements seraient :

2->4 , 2->6 , 2->8 , 3->9 , 2->10 , 5->10 , 3->12 , 4 ->12 , 2 ->14 , 5 ->15 , 2 ->16 , 4 ->16 , 3->18 , 6 ->18 , 2 -> 20 , 4 ->20 , 5 ->20 .

Chaque flèche indiquant le déplacement d'une pièce vers une case .

Vasimolo

Considérons la conjecture selon laquelle quelle que soit la position de départ (à savoir les nombres de [2;n] placés n'importe où sur [2;+infini[), l'algorithme s'arrête.

Une première remarque : étant donnée une position, en la décalant de PGCD(2;3;...;n), on obtient une position équivalente.

Maintenant, si la conjecture est fausse, ça peut être de deux façons : soit il y a "bouclage" (les mêmes positions se répètent indéfiniment à décalage près), soit il y a "divergence non bouclée", c'est-à-dire qu'il y a une infinité de positions différentes à décalage près qui apparaissent.

S'il existe une position qui aboutit à un bouclage avec les nombres de [2;n], alors il existe une telle position avec les nombres de [2;n+1] : il suffit de réaliser la même position en rajoutant le nombre n+1 quelque part à gauche, comme on joue en priorité avec les nombres de [2;n], n+1 restera immobile pendant que ses petits copains s'amusent sans lui.

Si on suppose au contraire qu'aucune position pour aucun n ne permet de bouclage, alors je pense qu'on peut démontrer qu'il n'y a pas non plus de "divergence non bouclée", je vais essayer de le faire proprement.

Par contre, démontrer qu'il n'y a pas de bouclage, c'est une autre paire de manche, je pense. Peut-être existe-t-il un poids strictement décroissant qui permette de le faire ?

Ton programme est correct également, Enigmatus !
Juste une petite remarque: tu as 10 mouvements de moins que le nombre max atteint si n = 10, puisque ton 1er mouvement atteint 11.

Oui, bien sûr, PPCM

Bonsoir Nodgim

Le cas n=7 est amusant à faire sur une grille avec des pions numérotés mais le plus intéressant est de savoir si on peut prévoir le blocage des déplacements ( attention le mouvement perpétuel se répète indéfiniment à l'identique , ce n'est pas le problème ici ) . La question peut avoir une solution simple ou déboucher sur un gouffre genre Syracuse , on ne peut pas savoir , mais le problème est intéressant

Vasimolo

@nodgim :
Ah oui, je n'avais lu que la première partie de la phrase : ...et à placer J dans la 1ère case libre qui suit le jeton le plus avancé.

J'ai maintenant 228 mouvements avant l'arrêt pour 10 jetons, et seules les postions finales des 2 jetons les plus proches sont modifiées.

C'est OK Vasimolo.
Je ne pense pas que les résultats apporteront grand chose pour l'analyse théorique, ils donnent en revanche une forte présomption pour l'arrêt ou non pour tout n.