$x_m$ termina con molti zeri
$x_m$ termina con molti zeri
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.
Re: $x_m$ termina con molti zeri
Wow, tribonacci numbers!
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: $x_m$ termina con molti zeri
c'eri tu oggi a Torino?
P.S: problema carino! (peccato averne sentito la soluzione senza averci provato...)
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)
Re: $x_m$ termina con molti zeri
Tu dici?Drago96 ha scritto: c'eri tu oggi a Torino?
The only goal of science is the honor of the human spirit.
Re: $x_m$ termina con molti zeri
mi sono incuriosito molto al problema e mi piacerebbe conoscerne la soluzione... qualche anima pia che già la conosce me la manderebbe per pm??
Re: $x_m$ termina con molti zeri
Invito Drago (che ancora non ho capito chi è) a ripetere la dimostrazionepatatone ha scritto:mi sono incuriosito molto al problema e mi piacerebbe conoscerne la soluzione...
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.
Re: $x_m$ termina con molti zeri
TI propongo le idee chiave della soluzione: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??
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
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
Re: $x_m$ termina con molti zeri
Come dimostro il punto 2??
Re: $x_m$ termina con molti zeri
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]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: $x_m$ termina con molti zeri
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..scambret ha scritto:Come dimostro il punto 2??
The only goal of science is the honor of the human spirit.
Re: $x_m$ termina con molti zeri
Un bound molto grezzo su quanto puo' valere tale periodo qui
The only goal of science is the honor of the human spirit.
Re: $x_m$ termina con molti zeri
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..
-
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: $x_m$ termina con molti zeri
Anche io forse non ho ben capito quello che intendete
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?
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
Re: $x_m$ termina con molti zeri
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
The only goal of science is the honor of the human spirit.
Re: $x_m$ termina con molti zeri
gli esempi banali sono fondamentali per capire dove le cose non funzionano!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?
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).