Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 02-04-2018 12:12:49

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

premier dz 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.

  • |
  • Répondre

#0 Pub

 #2 - 02-04-2018 21:12:57

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Pemier de cordé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 cordér

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... smile

 #4 - 02-04-2018 23:01:20

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Pemier de cordé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

premizr de cordé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 : 3801

Premier 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 e cordé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

premier dr 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 : 3801

premiee 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 : 3801

Premierr 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

oremier de cordée

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,382E+3

Premier de corddée

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

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 : 3801

prrmier de cordé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 cordéé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

premuer 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) :

Code:

num_mouvement=  239 
num_case   50 =>   10
num_case  154 =>   11
num_case  171 =>    9
num_case  208 =>    8
num_case  221 =>    6
num_case  235 =>    5
num_case  236 =>    4
num_case  237 =>    3
num_case  238 =>    7
num_case  239 =>    2

 #16 - 04-04-2018 16:58:41

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Premier de coordé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 : 3801

przmier de cordé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

premier dz cordée

Oui, bien sûr, PPCM smile

 #19 - 04-04-2018 17:28:50

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

Premier de codré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,382E+3

Prremier de 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 smile

Vasimolo

 #21 - 04-04-2018 19:58:08

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Premier de crodé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

Premeir de cordée

@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,382E+3

premier dz cordé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 smile

Vasimolo

 #24 - 05-04-2018 15:10:49

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3801

Premier e 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 : 3801

Premie 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....

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete