|
#1 - 02-04-2018 12:12:49
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
premiee de cordée
Bonjour @ tous.
Voici un algorithme curieux :
Vous disposez de cases numérotées dans l'ordre croissant des entiers naturels de 2 à .... Vous disposez de 6 jetons numérotés de 2 à 7 placés dans l'ordre dans les cases 2 à 7. Vous pouvez faire un Mouvement si une case occupée par un jeton J porte un numéro divisible par un numéro porté par un jeton K placé avant cette case. Un Mouvement consiste alors à avancer K dans cette case et à placer J dans la 1ère case libre qui suit le jeton le plus avancé. La priorité de mouvement est donnée dans l'ordre pour K du plus petit au plus grand numéro. Enfin, quand un jeton peut avancer, s'il a le choix, il doit le faire sur la case la plus proche.
A t'on affaire à un mouvement perpétuel ?
Bon amusement.
#2 - 02-04-2018 21:12:57
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
premier de coedée
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 ?
#3 - 02-04-2018 21:23:04
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
Premier de corrdée
Salut !
Bon, pas simple à appréhender ces règles...
Si je ne me suis pas trompé dans ma suite, je m'arrête à : Jeton 7 sur 101 6 sur 102 4 sur 104 5 sur 105 2 sur 106 3 sur 107
J'espère que c'est bon car je l'ai fait à la main et je n'ai pas trop envie de recommencer...
#4 - 02-04-2018 23:01:20
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Premier de corrdée
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é.
#5 - 03-04-2018 00:18:08
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
Premier de ccordée
Bon, effectivement je n'avais pas compris correctement... J'avais compris :
Vous pouvez faire un Mouvement si une case occupée par un jeton J porte un numéro divisible par un numéro porté par un jeton K placé avant cette case.
234567 -325674 -3-52746 Et là, malentendu :
La priorité de mouvement est donnée dans l'ordre pour K du plus petit au plus grand numéro.
Je faisais : ---537462 C'est ma faute, il faut que je recommence...
#6 - 03-04-2018 08:48:29
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
premuer de cordée
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 !
#7 - 03-04-2018 10:39:06
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
Premier de corddée
Bon, je trouve après l'avoir fait 2 fois le même résultat : Jeton 7 sur 70 6 sur 78 5 sur 80 3 sur 81 2 sur 82 4 sur 83 J'espère que ce coup-ci c'est bon...
#8 - 03-04-2018 11:00:57
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Preimer de cordée
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...
#9 - 03-04-2018 17:38:03
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Permier de cordée
@ Ebichu: ton programme marche bien !
Je pense que l'arrêt se généralise pour tout n, même si on change l'ordre de départ. Maintenant, vouloir prédire l'arrêt ou prouver le non-arrêt pour tout n me parait impossible. En revanche, pour un n donné, on est capable de connaitre la réponse dans l'un ou l'autre des cas.
J'ai commencé à la main avec les jetons de 2 à 11, comme ça pour voir.
#10 - 03-04-2018 18:05:50
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Prmeier de cordée
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 !
#11 - 03-04-2018 19:36:34
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Premier de cordé
Voici les résultats pour certaines valeurs de n, avec la position de départ classique 234...n : je donne le nombre d'étapes de calcul avant que cela termine.
n = 4 etapes : 1 n = 5 etapes : 6 n = 6 etapes : 17 n = 7 etapes : 76 n = 8 etapes : 111 n = 9 etapes : 230 n = 10 etapes : 229 n = 11 etapes : 228 n = 12 etapes : 227 n = 13 etapes : 3646 n = 14 etapes : 3645 n = 15 etapes : 3644 n = 16 etapes : 13213 n = 17 etapes : 47742 n = 18 etapes : 52781 n = 19 etapes : 55210 n = 20 etapes : 55209 n = 21 etapes : 55208 n = 22 etapes : 314857 n = 23 etapes : 1758726 n = 24 etapes : 1758725 n = 25 etapes : 1758724 n = 26 etapes : 1758723 n = 27 etapes : 1758722 n = 28 etapes : 1758721 n = 29 etapes : 1758720 n = 30 etapes : 1758719 n = 31 etapes : 1758718 n = 32 etapes : 233220717
On remarque que le calcul (n+étapes+1) donne le nombre bloquant qui contient beaucoup de diviseurs, et que pour n=9...12, ou pour n=13...15, ou n=19...21, ou n=23...31, ce nombre bloquant est le même.
#12 - 03-04-2018 22:57:34
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
Premier dde cordée
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
#13 - 04-04-2018 08:44:03
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Premier de corée
@ Vasimolo: c'est bien ça.
@ Ebichu : Super pour ces données !
Je vais analyser un peu, s'il y a des commentaires intéressants, je ne manquerais pas d'en faire part.
#14 - 04-04-2018 10:53:44
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Premier de crdée
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 ?
#15 - 04-04-2018 13:32:30
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
Premiier de cordée
Bonjour, J'ai finalement programmé le bidule. Pour comparer avec les autres résultats, voici ce que j'obtiens pour 10 jetons (arrêt après 239 mouvements) :
#16 - 04-04-2018 16:58:41
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Premier e cordée
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.
#17 - 04-04-2018 17:01:41
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Premier de codée
@ Ebichu : tes réflexions, pas encore tout à fait abouties, m'empêchent pour l'instant de donner des commentaires sur tes résultats.
Pardon, mais de quel PGCD parles tu ? ne s'agirait il pas plutôt de PPCM ?
#18 - 04-04-2018 17:26:37
- Ebichu
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 888
Prmeier de cordée
Oui, bien sûr, PPCM
#19 - 04-04-2018 17:28:50
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
Premier d cordée
nodgim #16 a écrit: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.
Je ne comprends pas ta remarque. Il y a des mouvements où la dernière case occupée ne bouge pas. Par exemple, après le 8ème mouvemnet, on va jusq'à la case 19, et c'est toujours le cas pour les 2 mouvements suivants.
#20 - 04-04-2018 19:36:54
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
Premier ed cordée
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
#21 - 04-04-2018 19:58:08
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Premier de cordéée
@ Enigmatus: 1 mouvement, c'est un jeton qui en chasse un autre placé devant lui. Cet autre est envoyé juste devant le jeton le plus avancé. On a donc bien pour chaque mouvement l'occupation d'une case supplémentaire. Cela dit, ce n'est pas très important pour notre sujet.
@ Vasimolo : Pas un mouvement perpétuel ? Voire. ça dépend comment on voit les choses. En tout cas, je suis d'acccord avec toi qu'on ne peut pas prédire grand chose avec un algo pareil. Et ça ressemble en effet à la difficulté de Syracuse, du fait du décalage vers l'avant. Ici, les nombres portés par les jetons sont confrontés à leurs multiples portés par les cases. Et pour l'instant, il semble que ce soit les cases qui s'arrrangent pour bloquer les jetons à un moment ou à un autre.
Je redonne un peu de temps au sujet, les programmeurs intéressés peuvent s'y essayer.
#22 - 04-04-2018 20:29:03
- enigmatus
- Expert de Prise2Tete
- Enigmes résolues : 0
- Messages : 561
premier de cordéz
@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.
#23 - 05-04-2018 12:04:54
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
premier de cirdée
Pour revenir à la question initiale , la progression s'arrête ( sauf erreur ) avec 2->82 , 3->81 , 4->83 , 5->80 , 6 ->78 et 7->70 .
J'attends de voir les prospections informatiques pour voir s'il y a espoir de mettre un peu d'ordre dans ce problème franchement amusant
Vasimolo
#24 - 05-04-2018 15:10:49
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
remier de cordée
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.
#25 - 07-04-2018 10:42:46
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
premiet de cordée
Et si je vous demandais à partir de quelle case les jetons 2 à 7, étant placés dans l'ordre décroissant et sans espace, l'un au moins pouvait atteindre 0, les cases étant numérotées dans l'ordre décroissant ?
Là on est davantage dans le domaine de la preuve formelle....
|
|