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 - 04-01-2018 09:49:05

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

suited pérodiques

Bonjour @ tous.

Soit "a" un entier naturel donné , et u0 une suite de  " a " chiffres.
u n = la suite des carrés des chiffres de u ( n-1 ) pris dans l'ordre, suite limitée à " a " chiffres.

Exemple : 2457 --->4;16;25;49 dont on ne retient que les 4 premiers chiffres soit 4162.

La suite u est forcément périodique. Il faut donner les périodes de u en fonction de " a " et de u0.

Bonne recherche et ne vous laissez pas enfumer....

  • |
  • Répondre

#0 Pub

 #2 - 04-01-2018 11:45:12

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

Suites pérodiquess

Bonjour Nodgim

Je suppose que tu veux dire que la suite va finir par boucler et que tu demandes la "taille" de la boucle .

Vasimolo

 #3 - 04-01-2018 12:48:24

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

Suites péérodiques

Oui Vasimolo, la suite va nécessairement reboucler sur elle même, c'est à dire il y aura u (n+k) = u (n). C'est  " k " qui est demandé.

Le terme " période " est mal approprié ? En fait elle sera périodique à partir d'un certain rang.

 #4 - 04-01-2018 14:27:18

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1494
Lieu: Coutiches

uSites pérodiques

Salut, Intéressant !

Supposons que la suite ne boucle pas, un terme n'ayant qu'une image, cela signifierait qu'il y a un nombre infini de termes possibles pour ne pas retomber sur un terme ayant déjà été utilisé.
Or il n'y en a que 10 000 possibles, la suite boucle donc forcément...

 #5 - 04-01-2018 15:45:44

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 971

suites péeodiques

1111 est un point fixe.

 #6 - 04-01-2018 16:30:39

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

Suiets pérodiques

@ Golgot : oui, comme chaque nombre de la suite est restreint par la norme de " a " chiffres, dont la quantité est finie, il y a forcément rebouclage, la suite est périodique à partir d'un certain rang.

@ Masab: un début de réponse avec 1111, suite périodique de période 1. A remarquer qu'on a aussi ce résultat avec des zéros et des as mélangés.

Il faut maintenant résoudre pour les autres nombres. Et aussi pour "a" quelconque.

il y a encore un peu de travail, mais ne vous laissez pas enfumer....

 #7 - 04-01-2018 19:28:26

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 971

suites pérodiqueq

Pour a=4, voici les 8 cycles d'ordre 4 :
[1003, 1009, 1008, 1006, 1003]
[1013, 1019, 1018, 1016, 1013]
[1036, 1093, 1081, 1064, 1036]
[1103, 1109, 1108, 1106, 1103]
[1113, 1119, 1118, 1116, 1113]
[1136, 1193, 1181, 1164, 1136]
[1361, 1936, 1819, 1641, 1361]
[3616, 9361, 8193, 6418, 3616]

Il semble que les périodes soient toutes égales à 1 ou 4.
Il semble aussi que pour a quelconque il y a exactement
[latex]2^{a-1}[/latex] cycles d'ordre 1
[latex]2^{a-1}[/latex] cycles d'ordre 4

Voilà ! Reste à le prouver...

 #8 - 04-01-2018 20:00:28

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

Suites péroiques

Je dirais que la suite est périodique (à partir d'un certain rang) de période 4, sauf dans le cas où les a-1 premiers chiffres de u0 sont dans {0;1} et où le dernier chiffre de u0 est dans {0;1;2;4;5;7} : la période vaut alors 1.

En fait, seul le premier chiffre de u0 différent de 0 ou 1 a de l'importance, tout ce qui est à droite de ce chiffre va se faire éjecter vers la droite au bout d'un certain temps.

 #9 - 05-01-2018 08:09:18

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

Suittes pérodiques

@ Masab :
Tu as déja bien débroussaillé le problème, reste en effet à analyser tout ça.

@ Ebichu :
Ton analyse est la bonne. Il manque toutefois encore la rédaction de la preuve, ce n'est pas bien long.

 #10 - 05-01-2018 10:43:46

LeJeu
Passionné de Prise2Tete
Enigmes résolues : 25
Messages : 74

Suitess pérodiques

Quel que soit le nombre "a" c'est le premier chiffre de U0 ( différent de 1) qui va imposer la suite Un

les chiffres de Un sont poussés vers la droite
par exemple pour a = 4
u0 = 9...
u1 = 81..
u2 = 641.
u3 = 3616

donc si u0 commence par 9 8 6 ou 3
en continuant on trouve Un de périodicité 4 de le forme
9 361 361 361.....
8 193 619 361...   
6 418 193 618...
3 616 164 181...
9 361 361 361...

si U0 commence par 7 , U1 commence par 4
si U0 commence par 5 , U1 commence par 2
si U0 commence par 2 , U1 commence par 4
si U0 commence par 4 , U1 commence par 16

donc si U0 commence par 7 5 2 4,
on trouve Un commençant par 1 et de périodicité 4 comme ci dessus
19 361 361 361.....
18 193 619 361   
16 418 193 618
13 616 164 181
19 361 361 361

enfin si u0 commence par 1 on cherche le 1° chiffre différent de 1 ou 0 pour conclure
soit une suite stationnaire de 1 et de 0 ,
soit on retombe sur les cas précédents


merci Nodgim pour ce joli pb.

 #11 - 05-01-2018 15:23:08

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

Suiites pérodiques

Ton analyse est correcte, Lejeu, cependant tu ne donnes pas vraiment de preuve. Elle est courte, mais il faut l'exhiber du constat que tu as fait.

Courage.

 #12 - 05-01-2018 15:36:00

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 971

Suites pérodiquees

Preuve pour a=1.
1 -> 1
2 -> 4 -> 1
3 -> 9 -> 8 -> 6 -> 3
5 -> 2 -> 4 -> 1
7 -> 4 -> 1
Donc 1 -> 1 est le seul 1-cycle
3 -> 9 -> 8 -> 6 -> 3 est le seul 4-cycle

Preuve pour a=2.
D'après ce qui précède, les 1 cycles commencent par 1* .
Les 4-cycles contiennent 1* ou 3* .
D'où 2 1-cycles et 2 4-cycles :
10 -> 10
11 -> 11
13 -> 19 -> 18 -> 16 -> 13
36 ->  93 ->  81 ->  64 ->  36

Preuve pour a=3.
Les 1-cycles sont de la forme 10* ou 11*.
Les 4-cycles contiennent 10* ou 11* ou 13* ou 36*.
D'où 4 1-cycles et 4 4-cycles :
100 -> 100
101 -> 101
110 -> 110
111 -> 111
103 -> 109 -> 108 -> 106 -> 103
113 -> 119 -> 118 -> 116 -> 113
136 -> 193 -> 181 -> 164 -> 136
361 ->  936 -> 819 -> 641 ->  361

 #13 - 05-01-2018 19:03:29

LeJeu
Passionné de Prise2Tete
Enigmes résolues : 25
Messages : 74

quites pérodiques

C'est vrai que la preuve était à peine murmurée.. je complète

Je dis que si  l'on part de 9 8 6 ou3 on obtient à un moment
U(n) = 9 361 361 ..... ( un 9 suivi   x fois du paquet de trois chiffres 361) de longueur supérieur à a

en effet  si  on part de 9  on trouve un U(n) commençant par 9361
81
641
36161
9361361

idem en partant de 8 6 ou 3

Puis en partant de 9361 , on le décompose en 9 suivi de 1 paquet '361'

le 9 se transforme en 4 tour en :
81
641
36161
9361361

et le 361 se transforme en 4 tour
936
819
641
361

donc le 9 suivi de 1 paquet '361' se transforme en 9 suivi de 3 paquets '361'

si on recommence en gardant   9 suivi de 2 paquets '361'
en séparant en (9 361)(361)
en 4 tour on a donc 9 suivi de 4 paquets de '361

si on recommence
on décompose en( 9 suivi de 3 paquets de '361' )(361)
en 4 tours on a donc 9 suivi de 5 paquet de '361'

ainsi de suite
pour obtenir à un moment donné U(n)= 9 suivi  de x paquets de trois chiffres 361 le tout de longueur supérieur à a
et on a alors U(n+4) =U(n)

 #14 - 05-01-2018 19:27:33

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

suites pérodoques

@ Lejeu: désolé ta démo ne tient pas puisque tu te trompes sur le nombre récurrent. Essaye de prolonger ton nombre, tu vas t'apercevoir que la belle mécanique se dérègle au dela du 10 ème chiffre. Et ça se démontre facilement.

@ Masab : bien, mais tu ne pourras pas procéder ainsi pour de plus grands nombres. Quelque chose t'échappe encore. Il ne faut pas se laisser enfumer par l'énoncé.....

 #15 - 06-01-2018 09:05:21

LeJeu
Passionné de Prise2Tete
Enigmes résolues : 25
Messages : 74

duites pérodiques

La nuit portant conseil, on oublie le 2ieme post et je viens compléter le 1°

- la seule chose importante est le 1° chiffre
( les autres seront poussés vers la droite, on ne s'en occupe pas))

- les chiffres 8,3,6,9 sont particuliers car en 4 transformations :
3->36161
6->64181936
8->819361936
9->9361361
et donc on retrouve le chiffre de départ en 1° position!

par cette simple propriété,
en partant d'un seul chiffre
toutes les 4 transformations on retrouve le nb précédent mais complété par de nouveaux chiffres ( peu importe la façon de les générer)

3
36161
3616116418193616

et donc  quelque soit 'a' on trouvera bien les 'a' premiers chiffres égaux après un certain nb  d'itérations

pour les chiffres 2,4,5,7
on trouve à chaque fois un nombre commençant par 16
le 1 est stationnaire ,et le 6 suit la règle précédente

pour le chiffre 1
on trouve le 1° chiffre différent de 1 et de 0 et on est ramené au 1° cas

 #16 - 06-01-2018 11:44:16

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

suutes pérodiques

C'est bien ça, Lejeu. Je l'aurais exprimé un peu différemment, mais bon c'est OK, bravo à toi !

 #17 - 07-01-2018 10:49:25

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

Suties pérodiques

Le temps est écoulé, vous pouvez voir les réponses.

L'énoncé était trompeur dès le départ. Pour un chiffre autre que 0 ou 1, l'algorithme engendre des nombres strictement croissants. Donc le 1er chiffre à gauche différent de 0 ou 1 repousse vers la droite tous les autres. Autrement dit, les autres chiffres ne servent à rien pour notre problème.

Pour le 1er chiffre différent de 0 ou 1, si c'est un 7,4,2 ou 5, on aboutira en 1er chiffre sur un 1, et 6 en 2ème chiffre. Pour les chiffres 6,3,9 et 8, on boucle sur une période 4.
Donc quel que soit le 1er chiffre à gauche autre que 0 ou 1, on tombe sur la boucle 6,3,9,8.

Or si on un 6 en k, on a donc un 6 en k+4, même rang dans le nombre.
Donc on trouve un 36 en k+1 et aussi un 36 en k+5.
et 936 en k+2 et 936 en k+6.
etc....

Donc non seulement au bout d'un certain nombre d'itérations on retrouve le même nombre sur une période 4, mais en plus on trouve toujours le même nombre modulo 4 quel que soit le nombre de départ ! hormis les 0 ou 1 à droite.

Merci @ tous pour vos réponses, abouties ou pas, l'important est de participer.

 

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 : Pif, Paf et ?

Sujets similaires

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