Arithmétique : fibonacci

par **lapras** » 30 Avr 2008, 00:46

Bonsoir,
démontrer que tout nombre entier naturel peut s'écrire comme la somme de nombre de la suite de fibonnaci dont les indices ne sont pas consécutifs.
donc pour tout n il existe (i , j , k , .... ) non consécutifs tel que
n = Fi + Fj + Fk + ....
les Fi étant les nombres de finonnaci définis par :
F0 = 1
F1 = 2
Fn+2 = Fn+1 + Fn

Source : olympiade américaine 2007
merci a gaara pour l'exo

par **Quidam** » 30 Avr 2008, 01:45

lapras a écrit:Bonsoir,
démontrer que tout nombre entier naturel peut s'écrire comme la somme de nombre de la suite de fibonnaci dont les indices ne sont pas consécutifs.
donc pour tout n il existe (i , j , k , .... ) non consécutifs tel que
n = Fi + Fj + Fk + ....
les Fi étant les nombres de finonnaci définis par :
F0 = 1
F1 = 2
Fn+2 = Fn+1 + Fn

Source : olympiade américaine 2007
merci a gaara pour l'exo

Petite précision : "des indices non consécutifs" si :

avec

cela veut-il dire

ou bien

tel que

et

ou encore "des indices non nécessairement consécutifs"

par **lapras** » 30 Avr 2008, 01:46

n = F_(i1) + F(i2) + ... + F(ik)

il n'existe pas j, m tels que
ij = im + 1

par **Quidam** » 30 Avr 2008, 02:10

lapras a écrit:n = F_(i1) + F(i2) + ... + F(ik)

il n'existe pas j, m tels que
ij = im + 1

Merci !

Bigre ! C'est plus dur que je le croyais...Je vais y réfléchir !

par **lapras** » 30 Avr 2008, 02:19

Non en fait la solution est tres simple ;)
Un conseil : tatonne a la main. (fais des exemples)

par **nodgim** » 30 Avr 2008, 10:34

Soit N tombe directement sur un nombre de Fibo, alors le problème est résolu.
Soit ce n'est pas un Nfibo. Il est compris entre 2 Nfibo, Fn et F(n+1), et l'écart entre N et Fn est forcément inférieur à F(n-1), de par la nature même de la suite Fibo. De proche en proche, on ne pourra donc jamais trouver dans la sommation de N, 2 nfibo consécutifs. :zen:

par **_-Gaara-_** » 30 Avr 2008, 10:38

nodgim a écrit:Soit N tombe directement sur un nombre de Fibo, alors le problème est résolu.
Soit ce n'est pas un Nfibo. Il est compris entre 2 Nfibo, Fn et F(n+1), et l'écart entre N et Fn est forcément inférieur à F(n-1), de par la nature même de la suite Fibo. De proche en proche, on ne pourra donc jamais trouver dans la sommation de N, 2 nfibo consécutifs. :zen:

Salut,

attention, ils ne doivent pas être consécutifs ! :++:

par **lapras** » 30 Avr 2008, 10:59

Oui c'est ca c'est un récurrence forte :
k : le plus grand entier tel que n >= Fk
cas d'égalité c'est fini
si n != Fk
alors
n = Fk + h
h un entier
h ne peut etre égal à Fk-1 + ....
car sinon Fk + Fk-1 = Fk+1 donc l'indice i du plus graand nombre de fibonnaci dans h est <= k-2
par récurrence, h est une somme de nbres de fibonnaci dont les indices ne sont pas consécutifs
c'est donc terminé :)

par **ThSQ** » 03 Mai 2008, 21:07

Réciproque (hard si ma mémoire est bonne) : Trouver toutes les suites telles que tout nombre puisse s'écrire ainsi (ie somme de nombres de la suite dont les indices ne sont pas consécutifs.)

par **venousto** » 05 Mai 2008, 22:04

fait un tour sur google à reve de phebus et venousto

il y a plein de preuve que la dpz marche

par **lapras** » 05 Mai 2008, 22:10

la dpz ? Qu'est ce que c'est ?

par **_-Gaara-_** » 05 Mai 2008, 22:25

lapras a écrit:la dpz ? Qu'est ce que c'est ?

division par zéro :++:

mais en fait je crois que venousto ne fait que flooder .... >.<

par **venousto** » 05 Mai 2008, 22:51

c'est vraiment important
si j'ai raison sur la dpz alors je suis un genie

par **lapras** » 05 Mai 2008, 22:54

S'il te plait évite de polluer nos beaux posts d'olympiades avec ta DPZ, monsieur le génie.

par **Imod** » 06 Mai 2008, 00:10

venousto a écrit:si j'ai raison sur la dpz alors je suis un genie

Désolé Chuck Norris l'a prouvé bien avant toi et lui au moins c'est un génie de la grosse baffe bête , laisse tomber et cesse de polluer STP :zen:

Imod

par **ffpower** » 06 Mai 2008, 00:10

lool,il nous avait manqué depuis que son topi c a été vérouillé..Mais ouais fais un nouveau topic plutot que du total HS(il a peur de se refaire vérouillé je crois^^)

par **lapras** » 06 Mai 2008, 00:14

Chuck norris a déjà compté jusqu'a l'infini.
Deux fois.

par **ffpower** » 06 Mai 2008, 00:23

Je crois meme qu il a reussi a compter les reels

par **_-Gaara-_** » 06 Mai 2008, 00:36

ffpower a écrit:Je crois meme qu il a reussi a compter les reels

et il a établit une relation d'ordre sur les complexes :ptdr: :ptdr:

par **Imod** » 06 Mai 2008, 08:33

_-Gaara-_ a écrit:et il a établit une relation d'ordre sur les complexes :ptdr: :ptdr:

Pour ça inutile de s'appeler Chuck Norris sauf si on veut qu'elle soit compatible avec la structure de corps :mur:

Imod

Arithmétique : fibonacci

Arithmétique : fibonacci

Qui est en ligne