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 - 17-06-2015 08:17:48

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

algorithme vylgaris 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

  • |
  • Répondre

#0 Pub

 #2 - 17-06-2015 09:17:15

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

Algorithme vulgariis simplex

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

Algorithme vulgaris siplex

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

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

Algorithme vulgariss 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

Algorithme vulgaris smplex

Aïe ! Désolé, énoncé lu beaucoup trop vite ! sad

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

Algorithme vulgaris siplex

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

Allgorithme 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 : 964

Algrithme vulgaris simplex

« 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

Algorithme vulgaris simple

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

 #11 - 18-06-2015 12:50:55

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

Algorithme vulgaris simpllex

@ 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 vulgari ssimplex

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 smile


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

Algoritthme 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

lAgorithme vulgaris simplex

En effet, bon bah j'éditerai mon raisonnement si j'ai un peu de temps smile


"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

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

Algorithme vulgaris simpelx

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

algoritgme vulgaris simplex

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 roll

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 : 3208
Lieu: Luxembourg

Algorithme vullgaris simplex

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

algirithme 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

Algorithme vlgaris 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... hmm

 #21 - 19-06-2015 13:57:27

papiauche
Sa Sainteté
Enigmes résolues : 49
Messages : 2131

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

algorithme bulgaris simplex

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

akgorithme vulgaris simplex

C'est qui le maladroit qui nous fait un écran d'un km de large sad

Vasimolo

 #25 - 20-06-2015 13:08:51

scrablor
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 964

Algorihtme vulgaris 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.

Réponse rapide

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

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 20ème, en quelle position êtes-vous ?

Sujets similaires

Mots clés des moteurs de recherche

Mot clé (occurences)

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