$x_m$ termina con molti zeri

Polinomi, disuguaglianze, numeri complessi, ...
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

$x_m$ termina con molti zeri

Messaggio da jordan »

Sia fissata la successione $x_1=2, x_2=3, x_3=6$, $x_{n+3}=x_{n+2}+x_{n+1}+x_n$ per ogni $n\ge 1$. Dimostrare che esiste un intero $m$ tale che $10^{2013} \mid x_m$.
The only goal of science is the honor of the human spirit.
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: $x_m$ termina con molti zeri

Messaggio da fph »

Wow, tribonacci numbers!
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
Drago96
Messaggi: 1147
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: $x_m$ termina con molti zeri

Messaggio da Drago96 »

:o c'eri tu oggi a Torino? :D

P.S: problema carino! :) (peccato averne sentito la soluzione senza averci provato...)
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $x_m$ termina con molti zeri

Messaggio da jordan »

Drago96 ha scritto::o c'eri tu oggi a Torino? :D
Tu dici? :)
The only goal of science is the honor of the human spirit.
patatone
Messaggi: 160
Iscritto il: 20 gen 2011, 19:25

Re: $x_m$ termina con molti zeri

Messaggio da patatone »

mi sono incuriosito molto al problema e mi piacerebbe conoscerne la soluzione... qualche anima pia che già la conosce me la manderebbe per pm?? :)
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $x_m$ termina con molti zeri

Messaggio da jordan »

patatone ha scritto:mi sono incuriosito molto al problema e mi piacerebbe conoscerne la soluzione...
Invito Drago (che ancora non ho capito chi è) a ripetere la dimostrazione :roll:
Ultima modifica di jordan il 23 apr 2013, 00:09, modificato 1 volta in totale.
The only goal of science is the honor of the human spirit.
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: $x_m$ termina con molti zeri

Messaggio da dario2994 »

patatone ha scritto:mi sono incuriosito molto al problema e mi piacerebbe conoscerne la soluzione... qualche anima pia che già la conosce me la manderebbe per pm?? :)
TI propongo le idee chiave della soluzione:
1) Chiamo $x_{-1}=0, x_0=1$. Allora vale $x_{n+3}=x_{n+2}+x_{n+1}+x_n$ per ogni $n\ge -1$.
2) La successione è fortemente periodica, cioè non ha antiperiodo, modulo qualsiasi numero.
3) Unendo i 2 fatti precedenti si ha che è infinite volte nulla modulo $10^{2013}$ e ciò dimostra la tesi.
Ultima modifica di dario2994 il 23 apr 2013, 18:39, modificato 1 volta in totale.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
scambret
Messaggi: 734
Iscritto il: 23 mag 2012, 20:49
Località: Acquarica del Capo

Re: $x_m$ termina con molti zeri

Messaggio da scambret »

Come dimostro il punto 2??
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: $x_m$ termina con molti zeri

Messaggio da fph »

Nota che la relazione di ricorrenza può essere rigirata anche per ricavare $x_n$ sapendo $x_{n+1}, x_{n+2}, x_{n+3}$. Quindi...
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $x_m$ termina con molti zeri

Messaggio da jordan »

scambret ha scritto:Come dimostro il punto 2??
Modulo $n$ le possibili "terne" di $(x_i,x_{i+1},x_{i+2})$ di residui sono in numero finito. Questo significa che i residui diventano periodici definitivamente..
The only goal of science is the honor of the human spirit.
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $x_m$ termina con molti zeri

Messaggio da jordan »

Un bound molto grezzo su quanto puo' valere tale periodo qui :roll:
The only goal of science is the honor of the human spirit.
scambret
Messaggi: 734
Iscritto il: 23 mag 2012, 20:49
Località: Acquarica del Capo

Re: $x_m$ termina con molti zeri

Messaggio da scambret »

La cosa che non mi spiego è che le terne sono finite, ma nessuno mi dice che modulo $10^{2013}$ la somma dei resti è 0. O è altamente probabile che stia rincretinendo..
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: $x_m$ termina con molti zeri

Messaggio da Gottinger95 »

Anche io forse non ho ben capito quello che intendete :oops:
Se per esempio prendo la ricorrenza \(x_{n+3} = x_{n+2} -x_{n+1}+x_n\), anche questa si può rigirare per ottenere \(x_n\), e perciò la terna \((x_{n+3},x_{n+2},x_{n+1})\) può assumere solo alcuni valori. Di fatto, se pongo \(x_1 = x_2 = x_3 = 1\), mi viene \(x_n=1\) per ogni \(n\), ed effettivamente è fortemente periodica, ma nessuno dei termini è divisibile per alcun numero. L'esempio è banale, ma la domanda in sè è: come dimostro che il periodo passa per tutti i valori modulo \(n\) e non solo per alcuni?
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $x_m$ termina con molti zeri

Messaggio da jordan »

Questo è il punto, infatti: le possibili terne sono in numero finito, quindi i resti diventeranno periodici. Se i resti diventano periodici modulo $m\ge 2$ con periodo $T(m)$ allora la "sequenza periodica di resti" è $a_0,a_1,a_2,\ldots,a_{T(m)-1}$. Noi conosciamo tre elementi consecutivi di questa sequenza (per inciso, $a_i:=a_j$ se e solo se $T(m) \mid i-j$ cosicchè la sequenza degli $a_i$ è definita per ogni $i$ intero). Adesso, ci disegnamo una circonferenza, fissiamo un verso di percorrenza, e disegniamo gli $n$ punti distinti $a_0,a_1,\ldots,a_{T(m)-1}$ in ordine. Dato che, una volta fissati $a_{n+1},a_{n+2},a_{n+3}$ possiamo ricavarci sia $a_{n+4}$ che $a_n$ (modulo $m$), allora è vero che possiamo ricavarci l'intera "sequenza periodica di resti" sia in senso orario che in senso antiorario. Spero adesso sia piu' chiaro :roll:
The only goal of science is the honor of the human spirit.
ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Re: $x_m$ termina con molti zeri

Messaggio da ma_go »

Gottinger95 ha scritto:L'esempio è banale, ma la domanda in sè è: come dimostro che il periodo passa per tutti i valori modulo \(n\) e non solo per alcuni?
gli esempi banali sono fondamentali per capire dove le cose non funzionano!
comunque, nessuno ti dice che la successione becchi tutti i resti! ti dice solo che, se ne becca uno, lo becca infinite volte. infatti poi si è dovuti tornare indietro e trovare $x_{-1}=0$ (o $x_{-2}=0$, non ricordo). se mi dai tre valori a caso per $x_0$, $x_1$ e $x_2$ la cosa si fa molto più oscura (e potrebbe benissimo essere falsa, direi).
Rispondi