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 - 16-09-2013 19:37:34

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

ebcore une suite.

Au sujet de la suite de Collatz, dite aussi de Syracuse, Paul Erdös a dit que les Mathématiques n'étaient pas prêtes pour résoudre ce problème.

Je propose donc ici une variante plus facile à aborder:
Soit n un entier, s'il est divisible par 3, on fait n/3, sinon on fait 2n-1, et on recommence.
Quelle sera dans N la part des nombres:
-qui donneront 1 ?
-qui partiront à l'infini ?
-qui auront une autre destinée ?

Bon amusement.

  • |
  • Répondre

#0 Pub

 #2 - 16-09-2013 20:29:35

SabanSuresh
Elite de Prise2Tete
Enigmes résolues : 45
Messages : 1951
Lieu: Paris

encore ube suite.

Tous les multiples de 3 donneront 1 à coup sûr.
Tous les nombres de la forme 3n+1 partiront à l'infini et y'en a 1/3 dans N.

 #3 - 17-09-2013 11:41:28

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 378

Encore une suit.e

Je fais un premier post, mais je n'ai pas encore découvert la clef complète...

Pour traiter ce problème, nous allons compter en base 3.

Les nombres divisibles par 3 sont ceux qui ont un zéro à droite. La division par 3 consiste à supprimer ce zéro à droite (et on recommence jusqu'à ce que l'on tombe sur le nombre 1, et c'est fini, ou sur le chiffre 1 ou 2 à droite).

Si un nombre se termine par 1, alors 2n-1 a pour chiffre des unités 1 et n'est donc pas divisible par 3, donc le terme suivant est à nouveau 2 X - 1 et la suite diverge.

Si un nombre n se termine par 2. il s'écrit 3k+2, son suivant est 2n-1=6k+4-1=6k+3, dont le suivant est 2k+1.
Si k est divisible par 3, alors 2k+1 se termine par 1, et la suite diverge
Si k est de la forme 3i+1 alors le terme 2k+1=6i+3, de terme suivant 2i+1 (et on "boucle dans le raisonnement avec i à la place de k)
Si k est de la forme 3i+2, alors le terme 2k+1=6i+5=3(2i+1)+2, qui se termine par 2. Le terme suivant est 6(2i+1)+4-1=12i+9, de terme suivant 4i+3 (et on repart dans 3 hypothèses sur i mod 3...).

En force brute excell, je n'ai vu aucun lien entre la structure des nombres se terminant par 2 et le caractère divergent ou pas de la suite.
Par contre, je n'ai trouvé aucun exemple de suite qui boucle.

Voila voila...

 #4 - 17-09-2013 18:34:15

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

Encore ue suite.

Saban: et 21 ?
Dylasse: il faut creuser un peu plus.
Les 2 premières réponses, d'auteurs émérites, me font dire qu'il faut aborder ce problème, à l'apparence plutôt facile, avec certaines précautions....

 #5 - 18-09-2013 10:04:16

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 378

encore une suute.

motivé par les propos de Nogdim, je poursuis...

au lieu de lister les nombres qui divergent ou pas, je vais me recentrer sur la question, et trouver la part de ceux qui divergent, ou plus exactement, la part de ceux qui auront un élément de leur suite avec 1 comme chiffre des unités.

Soit P cette proportion :
P=1/3 + 1/3 P2 + 1/3 (1/2 + 1/2 P2) , où P2 est la proportion de nombres avec 2 au chiffre des unité qui divergent.
Je détaille la formule :
+ 1/3, c'est la proportion des nombres avec un 1 à l'unité,
+ 1/3 P2, c'est la proportion des nombres vérifiant :  2 à l'unité et divergent,
+ 1/3 (1/2 + 1/2 P2), c'est la proportion de nombre avec un 0 à l'unité qui divergent (dans 50% des cas, il y a un 1 devant le(s) 0 ; dans 50% des cas, il y a un 2).

Il reste à déterminer P2. En reprenant les calculs de mon précédent post, un nombre de la forme 3k+2 a pour suivant :
- dans un tiers des cas, un nombre avec un 1 à l'unité
- dans un tiers des cas, un nombre formé de la même façon (2k+1) -> (2i+1) et on boucle, donc on retrouve la probabilité P2
- dans un tiers des cas, un nombre avec soit un 1, soit un 2, soit un 0.

(j’ai conscience de passer un peu vite sur l’équirépartition des i mod 3, mais la valeur de k ne semble pas influencer la valeur de i mod 3…)

D'où la relation :
P2 = 1/3 + 1/3 P2 + 1/3 (1/3 + 1/3 P2 + 1/3 (1/2 + 1/2 P2))
D’où P2 (1-1/3-1/9-1/18) = 1/3 +1/9 + 1/18
Soit : P2 (9/18) = 9/18

D’où P2 = 1

Ceci signifie que P=1, c’est-à-dire que la proportion de Nombres qui divergent (car avec un nombre avec un 1 à l’unité dans la suite) est de 100%.

Les autres cas :
- convergence vers 1 : il y a des cas mais de proportion nulle (bien que l’ensemble soit infini, puisque les 3^k sont dans cette liste)
- autre destinée : proportion nulle (et il n’y en a sans doute pas !).

 #6 - 18-09-2013 18:47:12

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

Encor une suite.

C'est OK Dylasse, tu as fait plus court que moi, bravo !
Tu devrais pouvoir conclure s'il existe des boucles ou pas. C'est plutôt assez basique comme démo, en fait.

 #7 - 19-09-2013 00:13:32

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 378

encpre une suite.

Merci de ton soutien sans faille Nogdim...
Montrons donc qu'il n'y a pas de "boucle", c'est à dire une suite qui repasse par la même valeur.
Raisonnons par l'absurde et supposons qu'une telle suite existe, appelons u son terme le plus petit.

u n'est pas de la forme 3k (car sinon k serait dans la suite et est inférieur à u)
u n'est pas de la forme 3k+1, sinon, on a vu que ça diverge
u est donc de la forme 3k+2, le terme suivant est 6k+3, le terme suivant est 2k+1, qui est inférieur à u, d'où contradiction.

Donc il n'y a pas de suite qui boucle.

Bon voilà... je crois que j'ai fini cette fois wink

 #8 - 19-09-2013 18:52:10

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

Encore une suite

C'est bon Dylasse, et cette fois encore tu as trouvé une autre démo que la mienne, je te dirai à la fin comment j'ai fait.
Bravo encore.

 #9 - 20-09-2013 22:44:23

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

encorr une suite.

Bonjour smile,

Si on regarde ce que donne la suite sur les premiers nombres, on obtient :

1 - 1 - 1 ...
2 - 3 - 1 ...
4 - 7 - 13 - 25 ...
5 - 9 - 3 - 1 ...

Donc apparemment soit la suite par vers l'infini, soit la suite stagne à 1.
On peut voir rapidement que les nombres de la forme 3k+1 génèrent des suites infinis (pour k<> 0). En effet 2(3k+1) - 1 = 3(2k) + 1 = 3K+1 donc un nombre de la forme 3k+1 génère un autre nombre de la forme 3k+1 mais plus grand.

On ne peut pas avoir de boucles car un nombre de la forme 3k+2 donne 6k+3 qui donne 2k+1. Après éventuellement d'autre divisions par 3, on obtient un nombre que l'on va appelé n qui est plus petit que le nombre 3k+2 de départ (et qui n'est pas multiple de 3).

-Si n = 1 alors la suite stagne à 1.
-Si n <> 1 et n =3k'+1 alors la suite par à l'infini
-Si n = 3k'+2 alors on obtiendra des nombres encore plus petit jusqu'à ce qu'on arrive à un des deux cas du dessus.

Mais pour l'instant je ne trouve pas de formule générale pour les nombres de la forme 3k+2 qui donne une suite stagnante hmm


Il y a sûrement plus simple.

 #10 - 21-09-2013 08:48:03

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

encire une suite.

Bonne entame Cogito, tu as presque trouvé la réponse pour l'éventuelle boucle, alors que...

 #11 - 21-09-2013 10:21:14

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

Encore ue suite.

Je donne la méthode que j'ai employée pour répondre aux 2 questions.

Pour la démo de l'impossibilité de boucle:
3n--->n strictement décroissant (suite géométrique de raison 1/3)
3n+1--->6n+1=3(2n)+1=3n'+1>3n+1 strictement croissant.
3n+2---->6n+3---->2n+1 strictement décroissant en 2 itérations (quasiment une suite géométrique de raison 2/3)
Tant qu'on ne tombe pas sur un 3n+1, la suite décroît strictement toutes les 2 itérations quand on commence par un 3n ou 3n+2. Si on tombe sur un 3n+1, ce sera forcément un nombre différent de tous les autres nombres rencontrés précédemment (groupe 3n+1) et ensuite la suite croît indéfiniment avec des nombres du groupe 3n+1. 

Part des nombres qui partent à l'infini:
Tous les +1 modulo 3, donc 1/3
Tous les +2 mod3 donnent 0mod3, et rejoignent donc les 0mod3 de départ. Le résultat de la division par 3 des 0mod 3 est: 1/3 de 0mod3, 1/3 de 1mod3 et 1/3 de 2mod3.
Donc les 2/3 des entiers donnent 2/9 de 1mod3.
Les 2/9 2mod3 rejoignent les 2/9 0mod3, ensemble (4/9) ils donnent 1/3 de 1mod3 soit 4/27.
De proche en proche:
1/3+2/9+4/27+...=1/3(somme des (2/3)^n quand n va de 0 à l'infini)=1/3(3)=1

La part des nombres qui partent à l'infini est de 100% dans N.

 #12 - 21-09-2013 13:01:04

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

encore une duite.

Je ne comprend pas ce que signifie la phrase :
"la part des nombres qui partent à l'infini est de 100% dans N"  hmm


Il y a sûrement plus simple.

 #13 - 21-09-2013 13:25:29

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

encore une quite.

Oui, ça peut paraitre bizarre de dire que la part dans N est 100% de nombres qui partent à l'infini, alors qu'on sait bien qu'il y en a qui donnent 1, une infinité même ! C'est toute la subtilité des limites.
J'aurais pu dire que c'est 99,99999...%

 #14 - 21-09-2013 14:39:09

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

Encore une sute.

C'est étonnant !

Il y a autant de nombres qui donnent 1 que d'entiers naturels et pourtant il  représente 0,000...01% des entiers naturels ! yikes

Si j'ai bien compris , certes il y a un infinité de 0 après la virgule, mais comme c'est un pourcentage d'une quantité infini cela représente quand même quelque chose !


Il y a sûrement plus simple.

 #15 - 21-09-2013 14:48:11

SabanSuresh
Elite de Prise2Tete
Enigmes résolues : 45
Messages : 1951
Lieu: Paris

Encore une suitee.

Mais si la part des nombres qui partent vers l'infini est de 100%. Les deux autres parts doivent être nulles, non ?

 #16 - 21-09-2013 15:07:10

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

encote une suite.

à mon avis le terme le plus "proche" serait "de mesure nulle" bien qu'ici je ne pense pas qu'il s'agisse de cela.


Il y a sûrement plus simple.

 #17 - 21-09-2013 15:29:14

SabanSuresh
Elite de Prise2Tete
Enigmes résolues : 45
Messages : 1951
Lieu: Paris

Encore une sute.

Oui. Les 3 parts doivent êtres "complémentaires", c-à-d, la part des nombres qui donneront 1 dans N (P1) + la part des nombres qui partiront à l'infini dans N (P2) + la part des nombres qui auront une autre destinée dans N (P3)= 100%. Or, si P2 = 100%, P1 = P3 = 0%. Mais ça ne marche pas, car 3 donne 1 et donc P1 n'est pas égal à 0%. Là, ça se contredit.

 #18 - 21-09-2013 15:47:22

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

encpre une suite.

Comme l'a fait remarquer nodgim, en vrai card(P1) = 0,0000...01% des entiers naturels

On peut écrire cela comme ça :
[TeX]card(P1)=\lim_{n\rightarrow +\infty}10^{-n} * card(\mathbb{N})[/TeX]
quand on passe à la limite on "obtient" [latex]0 * +\infty[/latex] ceci est une forme indéterminé qui ne se réduit pas forcément vers 0. Dans notre cas ils se trouve que cela se "réduit" à [latex]+\infty[/latex] ce qui est bien le cardinal de P1.

Les raisonnement avec les infinis sont souvent contre-intuitifs.
Par exemple l'ensemble des nombres pairs représente 50% des entiers.
et l'ensemble des multiples de 5 représente 20% des entiers.
Pourtant il y a autant de multiples de 5 que de multiples de 2 ou que d'entiers naturels.


Il y a sûrement plus simple.

 #19 - 21-09-2013 16:40:12

SabanSuresh
Elite de Prise2Tete
Enigmes résolues : 45
Messages : 1951
Lieu: Paris

encore une syite.

D'accord, j'ai compris à part la formule (car c'est pas de mon niveau).
Ça veut dire que sur un intervalle [0;1000000000000000000000000000000000], l'ensemble des nombres paire représente 50% des entiers et l'ensemble des multiples de 5 représente 20% mais sur [0;+infini], non. C'est ça ?

 #20 - 21-09-2013 18:10:13

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

Encoer une suite.

Les multiples de 5 représentent 20% de l'ensemble des entiers naturels, et exactement aussi 20% dans un intervalle qui finit sur un 5n (quoique, il ne faudrait pas oublier le 0 qui vient apporter une correction).
Pour le cas qui nous intéresse, ce 100% caractérise la raréfaction des nombres qui aboutissent à 1 au fur et à mesure qu'on se ballade dans les grands nombres. Les 3^n par exemple se raréfient très vite.
Dans le même ordre d'idée, et sans doute encore plus surprenant, les nombres premiers sont dans la même catégorie: on dit de ces ensembles infinis qu'ils ont une densité limite nulle.
On peut citer aussi le cas des carrés.

On peut comparer ces ensembles de densité nulle dans N en sommant leurs inverses: La limite peut être infinie (les premiers par exemple) ou finie ( les puissances d'un premier par exemple).

 #21 - 21-09-2013 18:51:49

SabanSuresh
Elite de Prise2Tete
Enigmes résolues : 45
Messages : 1951
Lieu: Paris

Encore ne suite.

D'accord. Merci smile

 

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