Cred că aceia care urmăresc şi acest forum şi cel de la FMI sînt puţini. Aşa că semnalez o problema care a stîrnit oarece dispute pe acesta din urmă:
http://fmi.unibuc.ro/forum/viewtopic.ph ... e1ae#14815
Poate dă cineva o mînă de ajutor...
L.O.
O problema de pe forumul FMI
Moderators: Filip Chindea, maky, Cosmin Pohoata
-
Liviu Ornea
- -
- Posts: 123
- Joined: Sun Sep 30, 2007 8:48 pm
- Contact:
-
Virgil Nicula
- Euler
- Posts: 622
- Joined: Fri Sep 28, 2007 11:23 pm
Pentru cei interesati, iata sirul caruia i se cere termenul general in link - ul amintit mai sus :
\( x_0=0\ ,\ x_1=1 \) si pentru orice \( k\in \mathbb{N}^* \) , \( \left\{\begin{array}{c}
x_{2k}=x_k\\\
x_{2k+1}=x_k+x_{k+1}\end{array} \) .
===========================================================
Imi permit sa am si eu o idee. Aceasta-i mai degraba o problema de informatica.
Se arata usor ca daca scrierea in baza \( 2 \) a numarului \( n \) este \( \overline {a_pa_{p-1}\ldots a_1a_0} \) ,
atunci \( \overline {\underline {\left|x_n=a_0\cdot x_m+x_{n-m}\right|}}\ \ (*) \) , unde \( \left\{\begin{array}{c}
n= \overline {a_pa_{p-1}\ldots a_1a_0}\\\\
m= \overline {a_pa_{p-1}\ldots a_1}\end{array} \) .
Dupa parerea mea, este mai usor de scris \( x_n=f(a_0,a_1,\ldots ,a_p) \) decat \( x_n=g(n) \) .
Relatia de "recurenta" \( (*) \) permite un program mai "economic" de generare a termenilor sirului.
Voi continua sa ma gandesc la ea. Cred ca aici se poate asocia lui \( n \) si un drum
intr-un graf pe "nivele" ale cifrelor din scrierea in baza doi a numarului \( n \) .
\( x_0=0\ ,\ x_1=1 \) si pentru orice \( k\in \mathbb{N}^* \) , \( \left\{\begin{array}{c}
x_{2k}=x_k\\\
x_{2k+1}=x_k+x_{k+1}\end{array} \) .
===========================================================
Imi permit sa am si eu o idee. Aceasta-i mai degraba o problema de informatica.
Se arata usor ca daca scrierea in baza \( 2 \) a numarului \( n \) este \( \overline {a_pa_{p-1}\ldots a_1a_0} \) ,
atunci \( \overline {\underline {\left|x_n=a_0\cdot x_m+x_{n-m}\right|}}\ \ (*) \) , unde \( \left\{\begin{array}{c}
n= \overline {a_pa_{p-1}\ldots a_1a_0}\\\\
m= \overline {a_pa_{p-1}\ldots a_1}\end{array} \) .
Dupa parerea mea, este mai usor de scris \( x_n=f(a_0,a_1,\ldots ,a_p) \) decat \( x_n=g(n) \) .
Relatia de "recurenta" \( (*) \) permite un program mai "economic" de generare a termenilor sirului.
Voi continua sa ma gandesc la ea. Cred ca aici se poate asocia lui \( n \) si un drum
intr-un graf pe "nivele" ale cifrelor din scrierea in baza doi a numarului \( n \) .
-
Filip Chindea
- Newton
- Posts: 324
- Joined: Thu Sep 27, 2007 9:01 pm
- Location: Bucharest
De fapt, aceasta problema chiar este foarte cunoscuta, numai ca în literatura... functiilor generatoare.
Sa ne uitam la sirul \( (a_k)_{k \ge 0} \), \( a_k = x_{k+1} \). Pentru \( k \ge 1 \),
\( \left\{ \begin{array}{c} a_{2k - 1} = a_{k - 1} \\ a_{2k} = a_{k} + a_{k - 1} \end{array} \right. \)
Inmultind relatiile cu \( X^{2k-1} \), respectiv \( X^{2k} \), si facând suma dupa \( k \ge 1 \), daca \( A(X) \) este seria de puteri formala în nedeterminata \( X \) a lui \( (a_n) \), obtinem
\( A(X) = (1 + X + X^2)A(X^2) \).
Deci, inductiv, \( A(X) = D_k(X) \prod_{j = 0}^k \left( 1 + X^{2^j} + X^{2^{j+1}} \right) \), si acum (nu stiu cât de riguros este), \( A(X) = D(X) \prod_{j \ge 0} \left( 1 + X^{2^j} + X^{2^{j+1}} \right) \). Este imediat ca \( D(X) \equiv 1 \), adica
\( A(X) = \prod_{k \ge 0} \left( 1 + X^{2^k} + X^{2^{k+1}} \right) \).
Termenul \( x_k \) nu este altceva decât coeficientul lui \( X^{k-1} \) în expresia (infinita) de mai sus (de aceea \( x_0 \) este luat, prin conv., \( 0 \)).
Obs. Interpretarea "informatica", daca vreti sa o numiti astfel, este ca termenul \( x_n \) numara reprezentarile lui \( n - 1 \) sub forma de puteri ale lui \( 2 \), nu mai mult de un exponent ales din fiecare multime \( \{1, 2\}, \{2, 4\}, \{4, 8\}, \{8, 16\}, ... \).
Exemplu. Se observa \( x_{18} = x_4 + x_5 = 4 \). Intr-adevar,
\( \begin{array}{rclc} 17 & = & 1 + 16 & (2) \\ & = & 1 + 8 + 8 & (1) \\ & = & 1 + 4 + 4 + 8 & (1)\end{array} \),
unde în paranteze am trecut numarul de reprezentari corespunzator (în primul caz, \( 16 \) poate fi ales în doua moduri).
Sa ne uitam la sirul \( (a_k)_{k \ge 0} \), \( a_k = x_{k+1} \). Pentru \( k \ge 1 \),
\( \left\{ \begin{array}{c} a_{2k - 1} = a_{k - 1} \\ a_{2k} = a_{k} + a_{k - 1} \end{array} \right. \)
Inmultind relatiile cu \( X^{2k-1} \), respectiv \( X^{2k} \), si facând suma dupa \( k \ge 1 \), daca \( A(X) \) este seria de puteri formala în nedeterminata \( X \) a lui \( (a_n) \), obtinem
\( A(X) = (1 + X + X^2)A(X^2) \).
Deci, inductiv, \( A(X) = D_k(X) \prod_{j = 0}^k \left( 1 + X^{2^j} + X^{2^{j+1}} \right) \), si acum (nu stiu cât de riguros este), \( A(X) = D(X) \prod_{j \ge 0} \left( 1 + X^{2^j} + X^{2^{j+1}} \right) \). Este imediat ca \( D(X) \equiv 1 \), adica
\( A(X) = \prod_{k \ge 0} \left( 1 + X^{2^k} + X^{2^{k+1}} \right) \).
Termenul \( x_k \) nu este altceva decât coeficientul lui \( X^{k-1} \) în expresia (infinita) de mai sus (de aceea \( x_0 \) este luat, prin conv., \( 0 \)).
Obs. Interpretarea "informatica", daca vreti sa o numiti astfel, este ca termenul \( x_n \) numara reprezentarile lui \( n - 1 \) sub forma de puteri ale lui \( 2 \), nu mai mult de un exponent ales din fiecare multime \( \{1, 2\}, \{2, 4\}, \{4, 8\}, \{8, 16\}, ... \).
Exemplu. Se observa \( x_{18} = x_4 + x_5 = 4 \). Intr-adevar,
\( \begin{array}{rclc} 17 & = & 1 + 16 & (2) \\ & = & 1 + 8 + 8 & (1) \\ & = & 1 + 4 + 4 + 8 & (1)\end{array} \),
unde în paranteze am trecut numarul de reprezentari corespunzator (în primul caz, \( 16 \) poate fi ales în doua moduri).
Life is complex: it has real and imaginary components.
