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 - 28-01-2016 16:27:33

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

Exercisse sur less suite

Au secour, mon prof m'a donnée un exo pour dans 72 heures, j'y compran rien mad

On définit la suite (Un) par :
U0 = 229
U(n+1) = 3124*Un si (1+Un) est divisible par 5, et E(Un/5) sinon (où E est la fonction partie entière).
Montrer que (Un) converge.

Cé tro dur !!!... Aidé moi sinon je vais avoir une sale note sadsadsad

Oublié pas vous avé que 72 heure lol

Question subsidiaire : et si U0 = 9 999 999 999 999 ?



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 28-01-2016 18:19:09

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

Exercisse ssur les suite

Je trouve U(n) > 0 pour n < 244058 et 0 ensuite
heureusement mon installation de python gère nativement les grands nombres smile

 #3 - 28-01-2016 18:51:49

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

Exercisse sur les suiite

Bravo w9Lyl6n, bonne réponse !

"Grands" comment exactement ?

 #4 - 28-01-2016 19:48:40

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

Exercissse sur les suite

arbitrairement grand smile

 #5 - 28-01-2016 22:58:49

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 374

Exericsse sur les suite

Assez marrant comme comportement cette suite. J'ai regardé rapidement sur un tableur :en variant les paramètres on trouve des suites convergentes, des cycliques, peut être des divergentes....

Je vais m'y pencher demain.

J'ai deux idée pour démarrer : la base 5 semble pratique pour appréhender cette suite et on remarque que l'hypothèse de récurrence est adaptée et que de plus, 3124 est dans cette base un nombre très particulier...

A force de voir dans les solution de problèmes d’arithmétique "il suffit de passer en base 2...", je vais m'y mettre, en espérant bien tomber...Car les changements de base quand on n'est pas habitué c'est délicat...

 #6 - 28-01-2016 23:00:03

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

exercisse sur les syite

@portugal : a+b) w9Lyl6n s'en est passé
c) oui

 #7 - 28-01-2016 23:02:41

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 374

Exercisse sur les siute

Merci pour le tuyau...j'avais retiré si vite... mais j'ai noté l'indice... ;=)
on va voir demain ce que ca donne...

et bravo pour la praisantation de l'eniygme trai simpa

 #8 - 29-01-2016 08:07:40

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

Exercisse sur les sute

Bonjour,
La suite semble diverger au départ, mais [latex]u_{244058}=0[/latex], ainsi que les valeurs suivantes.
[latex]u_{186838}[/latex], [latex]u_{186839}[/latex], [latex]u_{186874}[/latex], [latex]u_{186875}[/latex] sont des nombres à [latex]964[/latex] chiffres.

Inutile de préciser que je ne l'ai pas fait à la main…smile

 #9 - 29-01-2016 09:21:48

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

Exrecisse sur les suite

@enigmatus : bravo ! Effectivement, ta paresse te perdra smile

Je rajoute une question subsidiaire pour vous occuper un peu plus.

 #10 - 29-01-2016 16:57:07

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

Exercisse sur les suitee

C'est une étrange énigme que tu nous proposes là. En effet, il suffit de faire le calcul selon l'algo de l'énoncé et on arrive à zéro.
En travaillant en base 5, le nombre 299 est 1404. Comme il se termine par 4, il faut multiplier par 5^5-1, c'est à dire:
140400000
-00001404

Si le résultat se termine par autre chose que 4, on élimine purement et simplement le chiffre en question, et ainsi de suite jusqu'à tomber sur 4.
En réalisant 10 fois cette opération, il ne reste que 14 base 5. 8 opérations supplémentaires et on arrive à un nombre sans aucun 4, donc zéro.

Je me suis amusé à faire cette opération sur les nombres qui se terminent par 4 en base 5 jusqu'à 100 (décimal) et on finit toujours à zéro. Je suis à peu près sûr que c'est vrai pour tous les nombres, mais je n'en ai pas la preuve.

Il est à remarquer que c'est moins long qu'on pourrait l'estimer. L'algo est pourtant équilibré, puisqu'on ajoute 5 zéros en moyenne 1 fois sur 5, si on suppose le 4 équitablement réparti. Je dirais que c'est même anormalement court.

C'est un algo qui ressemble beaucoup à la suite de Syracuse. Quoique la suite de Syracuse nous réserve parfois des mauvaises surprises avec des longueurs...

 #11 - 29-01-2016 17:25:06

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

Exerisse sur les suite

@nodgim : je suis d'accord avec ton premier paragraphe, et le dernier est très bien vu.

Par contre, je ne suis pas d'accord avec le 2e : il faut plus de 18 opérations au total, tu as dû faire une erreur de calcul.

 #12 - 29-01-2016 17:54:37

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

exercisse sur lrs suite

Je ne suis pas trop décidé à refaire le calcul, c'est long et c'est vite fait de faire une erreur. En revanche, je crois avoir compris pourquoi ça allait aussi vite: Les 4, d'une opération à l'autre, apparaissent et disparaissent au gré des soustractions. Or on sait qu'une répartition hasardeuse autorise de longues chaines sans 4, et fréquemment. Or ces longues chaines font diminuer illico le nombre d'autant de chiffres.

Par ailleurs, l'éventualité d'une boucle est très peu probable. En effet, le nombre des 5 chiffres à droite (dans le cas du 299=14040) se décrémente d'une unité à la fois  (pas à toutes les opérations). Pour envisager une boucle, il faudrait arriver à, dans le cas de notre 299, au moins 630 opérations (passer de 4040 à 0000), afin de retrouver 14040 ou un nombre intermédiaire, par suppression du 1 à droite. On est quand même assez loin de ce risque (ou alors, c'est que je me suis planté dans les grandes largeurs pour les opérations...)

 #13 - 29-01-2016 18:31:24

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

Exxercisse sur les suite

Je vais donner tout de même un exemple complet des opérations pour le nombre 79 (304), dis moi si tu es d'accord:

304

30400000
-.......304=
30344141

303441400000-
-.......3034414=
303433310031

303400000
-.......3034=
303341411

303341400000
-.......3033414=
303333311031

FIN

soit 4 opérations

 #14 - 29-01-2016 19:57:53

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

Exerciisse sur les suite

@nodgim : Je suis d'accord avec ton calcul sur 304. Mais ça n'est pas aussi simple avec 1404...

 #15 - 30-01-2016 08:11:15

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

exerxisse sur les suite

Bon j'ai trouvé mon erreur et j'arrive à 26 opérations, mais sans garantie. Il y a tellement de chiffres que ce n'est pas évident du tout d'éviter les erreurs, même s'il ne s'agit que d'une soustraction. En fait, il faudrait laisser faire une machine...

 #16 - 30-01-2016 10:41:41

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

exercidse sur les suite

@nodgim : pour tes 3 phrases, dans l'ordre : "non", "oui", "oui".

 #17 - 31-01-2016 09:15:34

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

exeecisse sur les suite

Je vois. Tu as choisi un record. En le faisant en semi automatique, je ne suis pas au bout après 140 opérations. Et le nombre grandit, grandit....
Je sais qu'il n'y aura pas de boucle jusqu'à (299*5-299)* 2 environ, dans les 2400 opérations. Et ce serait une sacrée chance si au bout de ces 2400 opérations, on retombe sur le nombre initial ou un nombre intermédiaire.

Maintenant, compte tenu qu'il n'y a pas de boucle pour les petits nombres, que plus un nombre grandit moins on a de chance de trouver une boucle, le nombre grandit infiniment ou retombe à zéro.

Il n'y a pas de solution arithmétique autre que de faire ces opérations pour prouver que ça tombe à zéro. L'algo proposé est équilibré, puisqu'on trouve pour le nombre en base 5 un 4 sur 5 en moyenne, et que quand on tombe sur 4, on ajoute 5 chiffres. Comme pour la suite de Syracuse, c'est l'irrégularité qui domine: une longue chaine de chiffres sans 4 prend le dessus. Mais c'est assez logique: si pour un grand nombre, chaque chiffre est représenté uniformément, la répartition est souvent inégale, ce qui favorise l'atttraction vers le zéro. Il faut noter qu'après 1 opération, mise à part les 5 premiers chiffres, tous les autres sont recalculés. On rebat les cartes à chaque tour.

 #18 - 31-01-2016 10:50:09

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

Exercisse su les suite

@nodgim : je suis d'accord avec ton explication, sauf pour la phrase contenant le mot "attraction" que j'analyse différemment.

Reste à répondre à l'énigme, et comme tu l'as constaté, il n'y a qu'une façon de le faire smile

 #19 - 31-01-2016 18:15:49

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

exercissr sur les suite

Bon, je risquais pas d'arriver au bout...
Portugal, tu dis avoir trouvé des suites en boucle, tu confirmes ? Pour quel plus petit nombre ? Combien d'opérations ?

 #20 - 31-01-2016 18:31:35

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 374

Exercise sur les suite

Pas pour 3124. C'était avec un autre paramètre que j'ai testé mais je ne me souviens plus lequel. C'était une boucle d'au moins 30 termes...impressionnant...

Ma petite feuille Excel me permettait pas de conclure. J'étais content de l'astuce des 4 qui s'effacent également en base 5 mais ca menaît pas au bout helas...

Au fait 3124/3125 pas tout à fait équilibré...

 #21 - 31-01-2016 19:28:27

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

exercisse sur les syite

OK Portugal. Dans ce genre de suite, si on a des boucles, on les trouve assez vite dans les petits nombres.

Mon tableur n'a pas pu résoudre, parmi les nombres de 1 à 1000:

104
229
254
479
504
509
514
519
524
529
554
579
604
729
879
954
979

Peut être y a t'il un nombre commun à toutes ces suites montrueuses.

 #22 - 31-01-2016 19:29:19

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

exercisse qur les suite

@Portugal: quelle est ta remarque sur le 3124 ?

 #23 - 31-01-2016 19:49:21

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

Exericsse sur les suite

Félicitations à w9Lyl6n et enigmatus qui avaient trouvé, mais aussi à nodgim pour son analyse.

Il s'agit effectivement d'une suite dérivée de Syracuse. Si on change un peu la définition de la suite, en "U(n+1) = E(3124*Un/5) si (1+Un) est divisible par 5, et E(Un/5) sinon", si on suppose que le reste modulo 5 du terme suivant de la suite est un entier aléatoire entre 0 et 4, et si on néglige les arrondis des parties entières, alors à chaque étape, le terme de la suite est multiplié "en moyenne" par (3124/3125)^(1/5) soit environ 0,999936.

Avec la suite de Syracuse, à chaque étape, on multiplie "en moyenne" par racine(3)/2 ~ 0,866 : le retour vers 1 est toujours relativement rapide. Dans cette suite, par contre, le "vent" qui ramène vers 0 est très faible, ce qui fait que le comportement de la suite est proche d'une marche aléatoire sur Z. Or, d'une part, avec une marche aléatoire sur Z, il suffit d'attendre, elle reviendra vers 0 avec une probabilité 1 ; d'autre part, sur des très grandes échelles, le vent se fait sentir : en moyenne, le terme de la suite est divisé par 10 tous les 36000 termes. Donc, en 36 millions d'étapes, le nombre perd 1000 chiffres.

229 était un choix méchant : c'est le premier entier qui demande plus de quelques centaines d'étapes, mais il en demande déjà plus de 200000 pour retomber vers 0. Pour résoudre l'énigme, il faut donc accepter que seul l'ordinateur nous permettra de nous en sortir (sauf révolution des mathématiques), mais, pire, comme l'a noté enigmatus, on passe par des nombres à quasiment 1000 chiffres : il faut un programme capable de manipuler d'aussi grands entiers.

Mais on pouvait faire nettement plus méchant : (10^13-1), que j'ai proposé en question subsidiaire, demande un peu plus de 700 millions d'itérations pour revenir à 0. Le pire nombre que je connaisse, 191769, en demande quasiment 1,5 milliards, et passe par un nombre à plus de 67000 chiffres...

Pour finir, j'aime bien l'équilibre de cette suite : il semble qu'il n'existe pas de cycle autre que le cycle trivial en zéro, et elle converge très lentement ; mais en essayant de faire pire (par exemple, en remplaçant le rôle de 5 par 7 ou 11), on tomberait sur des suites qui convergent tellement lentement que même un ordinateur n'aurait pas le temps de finir le calcul.

 #24 - 31-01-2016 20:04:22

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

Exercisse sur les suie

@nodgim : voici les temps de vol pour les nombres qui te manquaient :

104    237
229    244058
254    76
479    202
504    30093
509    430
514    292
519    7474
524    664
529    190
554    2020
579    75626
604    226
729    11620
879    203
954    269
979    305

 #25 - 01-02-2016 08:16:45

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

exercisse sur les siite

Merci Ebichu. Mon tableur ne sait plus diviser correctement au dela de 13 chiffres, d'où le loupé avec des nombres comme 254.

Pour ma part, j'avais jeté un coup d'oeil sur les suites type Syracuse du genre :
(3n+k)/2 avec k impair. Et là on trouve des boucles, mais toujours pour les petits nombres. Au dela d'un seuil (variable) on n'en trouve plus.

Pour espérer avoir un début de réponse avec ce genre de suites, il faudrait déja, à mon avis, pouvoir prouver par exemple qu'un 3^n écrit en binaire comporte à peu près autant de 1 que de 0. Plus basique encore, prouver que la différence entre une puissance de 3 et la puissance de 2 immédiatement supérieure est un nombre distinct pour chaque puissance de 3.

Malgré l'indéniable efficacité des mathématiques, les connaissances sont très faibles par rapport à ce qui est ignoré.

 

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 ?

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