|
#1 - 17-06-2015 08:17:48
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Agorithme vulgaris simplex
Bonjour à tous. Prenez un nombre impair n et ajouter lui 1 au départ, divisez le par 2 autant de fois que possible, puis ajouter n au résultat, qu'on divisera encore par 2 autant de fois que possible, et ensuite ajoutez n et ainsi de suite. Normalement vous devriez toujours aboutir à 1. Oui mais pourquoi ?
Bon amusement
#2 - 17-06-2015 09:17:15
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
Algorithme vulgaris simpplex
Salut !
Ta suite est caractérisée par v0=2k+1 avec k dans N v(i+1)=v(i)/2 si v(i)est pair v(i+1)=v(i)+1 sinon
Soit la suite u(n) des valeurs impaires de cette suite (je passe volontairement toutes les valeurs paires qu'on divise par 2).
On a alors une suite décroissante car u(n+1)=[u(n)+1]/2^k Donc u(n+1)/u(n)=[1+1/u(n)]/2^k<=1 car 1/u(n)<=1 u(n) est donc décroissante
Calculons la limite l éventuelle : l=(l+1)/2^k d'où lx2^k=l+1 qui donne lx(2^k-1)=1 soit l=1
Et voilà !
#3 - 17-06-2015 09:58:27
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Algorithme vulgaris simlex
Non Golgot, tu as dû lire l'énoncé trop rapidement. Le 1 n'est ajouté qu'au début, ensuite on ajoute n. Ce n'est pas une suite décroissante.
#4 - 17-06-2015 18:11:20
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
Algorihme vulgaris simplex
Bonjour Nodgim
Ça a l'air assez simple mais sans LaTeX je n'ai pas trop envie de me lancer dans la rédaction d'une solution complète .
Si k est l'ordre de 2 dans Z/nZ c'est à dire le plus petit entier non nul tel que 2^k=1[mod n] , alors 2^k-1=n(1+2^v1+2^v2+...+2^vf) , les vi en ordre croissant ( ce n'est rien d'autre qu'une écriture binaire de (2^k-1)/n ) . Après il n'y a plus qu'à dérouler l'algorithme .
Vasimolo
#5 - 17-06-2015 18:38:36
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Allgorithme vulgaris simplex
Mouiiii....Vasimolo, y a de ça. Mais y a une démo assez courte, sans avoir besoin de faire appel aux connaissances arithmétiques.
#6 - 17-06-2015 22:03:50
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
algorithle vulgaris simplex
Aïe ! Désolé, énoncé lu beaucoup trop vite !
Essai 1 : 17-18-9-26-13-30-15-32-16-8-4-2-1 13 termes
Essai 2 : Voilà qui est très long ! 131-132-66-33-164-82-41-172-86-43-174-87-218-109-240- 120-60-30-15-146-73-204-102-51-182-91-222-111-242-121-252- 126-63-194-97-228-114-57-188-94-47-178-89-220-110-55-186-93 -224-112-56-28-14-7-138-69-200-100-50-25-156-78-39-170-85-216 -108-54-27-158-79-210-105-236-118-59-190-95-226-113-244-122 -61-192-96-48-24-12-6-3-134-67-198-99-230-115-246-123-254-127 -258-129-260-130-65-196-98-49-180-90-45-176-88-44-22-11-142 -71-202-101-232-116-58-29-160-80-40-20-10-5-136-68-34-17-148 -74-37-168-84-42-21-152-76-38-19-150-75-206-103-234-117-248 -124-62-31-162-81-212-106-53-184-92-46-23-154-77-208-104-52 -26-13-144-72-36-18-9-140-70-35-166-83-214-107-238-119-250 -125-256-128-64-32-16-8-4-2-1
196 termes !
#7 - 17-06-2015 23:21:39
- scrablor
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 965
Algorithme vulgaris siimplex
La sous-suite formée des valeurs impaires est strictement décroissante tant qu'elle ne prend pas la valeur 1. En effet, pour n>1, (n+1)/2<n et a fortiori (n+1)/4, (n+1)/8... sont strictement inférieurs à n.
Celui qui fuit les casse-tête ne vaut pas un clou.
#8 - 18-06-2015 08:06:44
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
amgorithme vulgaris simplex
@ Golgot: ces exemples confirment la conjecture mais ne constituent pas une preuve. @ Scrablor: Même lecture trop rapide de l'énoncé que Golgot ? Cependant, il est exact que les nombres impairs de cette suite sont tous inférieurs à n. Ceci ne prouve pas pour autant qu'on bouclera sur 1.
#9 - 18-06-2015 09:17:44
- scrablor
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 965
Algorithme vulgaris simlpex
« Toute suite décroissante minorée converge » est un outil trop fort ici. Il suffit de dire qu'il y a un nombre fini d'entiers naturels impairs inférieurs ou égaux à n, donc impossible d'avoir une suite infinie d'entiers distincts. Or, tant que (u+1)/2<u, la suite des impairs notés u décroît strictement. On aboutit donc à un entier p impair tel que (p+1)/2<p soit faux. (p+1)≥2p donne p≤1 et donc p=1.
Celui qui fuit les casse-tête ne vaut pas un clou.
#10 - 18-06-2015 12:30:33
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
Algrithme vulgaris simplex
Alors pour la démo, je modifie un peu la façon d'exprimer la suite de départ (appelée u(n)) en disant que si le terme est pair, on le divise par 2, sinon on lui ajoute le terme de départ u(0) et on divise par 2. J'appelle cette "nouvelle" suite v(n)
1ère étape :
Hypothèse de récurrence : v(n)<u(0) 1er cas : si v(n) pair alors v(n+1)=v(n)/2<u(0)/2<u(0) 2 : si v(n) est impair : v(n+1)=(v(n)+u(0))/2<u(0) Hypothèse également vérifiée au 1er rang donc l'hypothèse est vrai, ce qui signifie qu'il n'y a qu'un nombre fini de termes par lesquels la suite peut passer, c'est à dire que ça boucle !
2ème étape : Prouver qu'un terme ne peut avoir qu'un seul antécédent.
_D'abord tous les termes de la suite u(n) sont forcément strictement inférieurs à 2u(0), car il ne manque que le terme intermédiaire u(n+1)=u(n)+u(0)=2v(n+1)<2u(0) dans u(n) par rapport à v(n).
_Du coup 2 possibilités : 1/ Soit un terme de la suite est inférieur à u(0), auquel cas il ne peut pas provenir e l'ajout de u(0) au terme précédent, il a donc été divisé par 2 2/ Soit il est supérieur à u(0) et il ne peut pas avoir été divisé par 2 sinon le terme précédent serait supérieur à 2u(0) ce qui est impossible, on lui avait donc ajouté u(0). (3/ u(0) ne peut pas être atteint car ni 0 ni 2u(0) ne peuvent faire parti de la suite)
Puisque nous avons une boucle et que chaque terme ne peut avoir qu'un antécédent, alors on doit nécessairement retomber sur u(1)=u(0)+1, dont le seul antécédent possible est 1 !
J'espère avoir été assez clair...
#11 - 18-06-2015 12:50:55
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Algorithme vulgaris implex
@ Golgot: c'est parfait, bravo !! @ Scrablor: ce n'est parce que ça boucle que pour autant tu vas revenir à 1. Pourquoi ne bouclerais tu pas sur une autre valeur que 1 ?
#12 - 18-06-2015 14:43:25
- shadock
- Elite de Prise2Tete
- Enigmes résolues : 39
- Messages : 3334
algorithme vulgaris simpmex
Existence de la limite : Soit n un nombre impair : n=2p-1 n+1=2p
-Soit le nombre est une puissance de 2 auquel cas après p+1 divisions on trouvera 1 -Soit le nombre n'est pas une puissance de deux, auquel cas on trouvera un nombre impair plus petit que le précédent par ajout de 1.
On obtient donc une suite de nombres impairs décroissante et minorée par 1 puisque tout les nombres sont positifs et qu'on travaille avec des entiers.
On a donc prouvé l'existence de la limite, plus qu'à montrer qu'elle est unique.
Unicité : Pour cela supposons qu'il existe une autre limite impaire noté n' dans les entiers naturels différents de zéro.
Alors n'+1 est divisible par 2 et (n'+1)/2+1 est plus petit que n', par récurrence n' tend vers 1 quand le nombre d'itérations est suffisamment grand selon le nombre de départ.
Ce qui achève la démonstration.
Shadock
"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
#13 - 18-06-2015 16:02:12
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Allgorithme vulgaris simplex
Salut Shadock, Je me demande s'il n'y a pas une lecture trop rapide de l'énoncé. En effet, le 1 ajouté au départ ne sert qu'une fois, ensuite c'est n qu'on ajoute, et non pas 1. La suite n'est donc pas décroissante.
#14 - 18-06-2015 17:40:42
- shadock
- Elite de Prise2Tete
- Enigmes résolues : 39
- Messages : 3334
Algorithme vulgaris simpleex
En effet, bon bah j'éditerai mon raisonnement si j'ai un peu de temps
"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
#15 - 18-06-2015 18:49:35
- taedriel
- Amateur de Prise2Tete
- Enigmes résolues : 32
- Messages : 5
- Lieu: saint-lo
Algoriithme vulgaris simplex
Spoiler : [Afficher le message] bonsoir
tout d'abord, on prend un nombre n impair on ajoute 1 a ce nombre, il devient donc pair puis on divise ce nombre pair par deux jusqu'à ce qu'on ne puisse plus diviser le nombre cela veut dire que ce nombre est soit impair soit égal à 1
Si il est impair, on rajoute n le nombre de départ or un nombre impair additionner à un autre nombre impair donne un nombre pair puis on divise ce nombre pair par deux jusqu'à tomber sur un autre nombre impair ou sur1 si on tombe sur un nombre impair on recommence cette partie jusqu'à tomber sur 1
connaissez vous l'absurde ? c'est comme un dromadaire qui fait une course de sous marin...
#16 - 18-06-2015 19:35:14
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
algorithme vulgariq simplex
Bonsoir Taedriel, Même remarque que précédemment, qui te dit que ça ne va pas tourner en boucle en évitant le 1 ?
#17 - 18-06-2015 22:49:37
- scrablor
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 965
algorithme vulgaris simolex
Incroyable... on est plusieurs à faire la même erreur de lecture ! Mon idée de base ne marche pas car les impairs ne décroissent pas forcément. Par exemple, n=45 donne 46, 23, 68, 34, 17, 62, 31, 76, 38, 19, 64, 32, 16, 8, 4, 2, 1.
Il reste quand même vrai que les impairs sont inférieurs à n et que, par conséquent, les pairs sont inférieurs à 2n. Mais je ne vois pas pourquoi, partant de 45, je ne pouvais pas aboutir à 3 qui aurait généré une boucle
Edit : Je flaire une piste... il semble que n soit premier avec tous les autres termes de la suite, mais il est un peu tard ce soir !
Celui qui fuit les casse-tête ne vaut pas un clou.
#18 - 18-06-2015 23:59:57
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3221
- Lieu: Luxembourg
Algorithme vulgaris simple
Je rajoute 1, puis je divise k(1) fois par 2, puis je rajoute n, puis je divise k(2) fois par 2, etc, etc, je divise k(t) fois par 2 et je tombe sur 1.
Je remonte maintenant le processus à l’envers. Mon dernier nombre était 2^k(t), celui d’avant 2^k(t)-n, celui d’avant 2^k(t-1).( 2^k(t)-n) soit 2^[k(t-1)+k(t)]-n.2^k(t-1), celui d’avant 2^[k(t-1)+k(t)]-n.2^k(t-1)-n, etc, etc, et le premier (désolé mais latex ne semble pas marcher): 2^[som k(i) i=1 à t]-n.2^[som k(i) i=1 à t-1] -…-n.2^[k(1)+k(2)] -n.2^k(1)-1
Ce nombre est aussi égal à n, d’où: n = {2^[som k(i) i=1 à t]-1} / {2^[som k(i) i=1 à t-1]+…+2^[k(1)+k(2)]+2^k(1)+1} L’idée est de démontrer que tout nombre impair peut s’écrire de cette façon là. Ca ressemble d'ailleurs à une écriture en base 2. Mais je dois aller dormir. I’ll be back.
#19 - 19-06-2015 08:31:12
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
algorithmz vulgaris simplex
@ Scrablor et Francky: vous êtes sur la bonne voie. La solution est assez élémentaire, il ne faut pas chercher le compliqué. C'est juste une question de logique. J'en ai trop dit déja là.
#20 - 19-06-2015 09:19:57
- d0n32
- Amateur de Prise2Tete
- Enigmes résolues : 47
- Messages : 8
Alorithme vulgaris simplex
Est-ce que c'aurait à voir avec le fait qu'un jour ou l'autre, l'on doit toujours tomber sur un nombre pair puissance de 2 ? Pour la démo mathématique par contre...
#21 - 19-06-2015 13:57:27
- papiauche
- Sa Sainteté
- Enigmes résolues : 49
- Messages : 2131
alforithme vulgaris simplex
Je dirais:
Si le nombre est de la forme 2^n-1 le résultat est toujours 1.
Dans les autres cas, il y a au moins deux itérations. Leur résultat est par construction inférieur à n, on peut l'établir ainsi: (n+impair inférieur à n)/2<n. Il y a au maximum (n+1)/2 occurrences impaires possibles et la suite des résultats est donc au maximum égale aux impairs compris entre 1 et (n+1)/2.
Au plus tard à la (n+1)/2+1ème itération, un impair déjà connu va réapparaître. Quand un nombre réapparaît, c'est qu'il a le même antérieur et à rebours on peut remonter l'algorithme au début, c'est-à-dire à 1.
Conclusion:
On aboutit toujours à 1 en moins de (n+1)/2 occurrences et la suite est cyclique.
"Je ne lis jamais un livre dont je dois faire la critique. On se laisse tellement influencer." O. Wilde
#22 - 19-06-2015 17:13:39
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3802
Algorithme vulgaris ssimplex
Papiauche, oui, je crois que tu as compris, même si tu as passé vite sur ce qui t'apparait comme une évidence.
#23 - 19-06-2015 19:35:28
- fmifmi
- Passionné de Prise2Tete
- Enigmes résolues : 18
- Messages : 87
algorithme vulgatis simplex
si je comprends bien, la seule chose a démontrer est que la suite ne tourne pas en boucle et donc rencontrera une puissance de 2 qui aboutit toujours a 1. la je coince
#24 - 20-06-2015 12:47:01
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
Algorrithme vulgaris simplex
C'est qui le maladroit qui nous fait un écran d'un km de large
Vasimolo
#25 - 20-06-2015 13:08:51
- scrablor
- Expert de Prise2Tete
- Enigmes résolues : 49
- Messages : 965
Algorithme vulgarsi simplex
papiauche a écrit:Quand un nombre réapparaît, c'est qu'il a le même antérieur.
Je ne comprends pas... Pourquoi ne pourrions-nous pas avoir au bout d'un certain nombre d'étapes quelque chose du genre ...17+7=24, 12, 6, 3, 3+7=10, 5, 5+7=12, 6, 3... ? Bon, je sais, n=7 n'est pas un bon exemple, mais c'est pour éclaircir ma question.
Celui qui fuit les casse-tête ne vaut pas un clou.
Mots clés des moteurs de recherche
|
|