Aqui vai outra solucao: a e b sao raizes da equacao: x^2 - 6x + 1 = 0 ==> equacao caracteristica da recorrencia: R(n) = 6*R(n-1) - R(n-2)
R(0) = (1/2)*(a^0 + b^0) = 1 R(1) = (1/2)*(a^1 + b^1) = 3 Como queremos o ultimo algarismo de R(12345), basta olhar mod 10: R(3) == 6*3 - 1 == 17 == 7 R(4) == 6*7 - 3 == 39 == 9 R(5) == 6*9 - 7 == 47 == 7 R(6) == 6*7 - 9 == 33 == 3 R(7) == 6*3 - 7 == 11 == 1 R(8) == 6*1 - 3 == 3 Ou seja, R(7) == R(0) e R(8) == R(1) (mod 10). Logo, R(m) (mod 10) eh periodica com periodo 7. 12345 = 7*1763 + 4 == 4 (mod 7) ==> R(12345) == R(4) == 9 (mod 10) Logo, o ultimo algarismos de R(12345) eh 9. []s, Claudio. on 11.06.04 02:44, Ricardo Bittencourt at [EMAIL PROTECTED] wrote: > Pedro Costa wrote: >> >> 2) Se Rn=(1/2)*(a^n+b^n) onde a = 3+2sqrt(2), b = 3 2sqrt(2) >> e n = 0,1,2,3,4.. então R12345 é um inteiro. Seu algarismo das unidades é: > > Deve ter jeito fácil de fazer isso, mas só me > veio à cabeça o jeito difícil. > > Calcule a soma infinita de potências de z: > > sum[Rn*z^n]= > sum[(1/2)*z^n*(a^n+b^n)]= > (1/2)*sum[(az)^n+(bz)^n]= > (1/2)*(1/(1-az) + 1/(1-bz))= (soma da pg infinita) > (1/2)*(1-bz+1-az)/((1-az)(1-bz))= > (1/2)*(2-(a+b)z)/((1-az)(1-bz)) > > Daí: > > 2(1-az)(1-bz)sum[Rn*z^n]=(2-(a+b)z) > 2(1-(a+b)z+abz^2)sum[Rn*z^n]=(2-(a+b)z) > > Notando que... > > a+b=3+2sqrt(2)+3-2sqrt(2)=6 > ab=(3+2sqrt(2))(3-2sqrt(2))=3^2-(2sqrt(2))^2=9-8=1 > > ...chegamos em... > > 2(1-6z+z^2)sum[Rn*z^n]=2-6z > > Abrindo a soma infinita e igualando os termos em z^n: > > 2(1-6z+z^2)(R0+R1z+R2z^2+....)=2-6z > > 2R0 = 2 > 2R1z + (-12)R0z = -6z > 2R2z^2 + (-12)R1z^2 + 2R0z^2 = 0 > 2R3z^2 + (-12)R2z^2 + 2R1z^2 = 0 > ... > > Daí podemos ver que: > > 2R0=2 => R0=1 > 2R1-12R0=-6 => 2R1-12=-6 => 2R1=6 => R1=3 > > e para n>=0: > > 2(Rn+2)-12(Rn+1)+2(Rn)=0 > Rn+2 = 6(Rn+1)-Rn > > Agora é só matar por congruências. Por indução > é fácil ver que todos os Rn são ímpares (base: R0 e R1 > são ímpares, passo: suponha todos os Rn menores que k > ímpares, então Rk+1=par*ímpar-ímpar=par-ímpar=ímpar), > de modo que só falta calcular mod 5. > > Mas a recorrência mod 5 fica assim: > > Rn+2=6(Rn+1)-Rn=1(Rn+1)-Rn=Rn+1-Rn > > Analisando os Rn para achar o período > (a indução pra mostrar que existe período é similar > à que usei pra mostrar que todos são ímpares): > > 1,3,2,4,2,3,1,3 e pronto o período é 6. > > Agora 12435=2057*6+3 e portanto temos que > pegar o quarto termo do período que é 4. > > Portanto R12345 mod 5 = 4, e como R1995 > é ímpar, então R12345 mod 10 = 9 (argh deu trabalho) > > ---------------------------------------------------------------- > Ricardo Bittencourt http://www.mundobizarro.tk > [EMAIL PROTECTED] "tenki ga ii kara sanpo shimashou" > ------ União contra o forward - crie suas proprias piadas ------ > ========================================================================= > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html > ========================================================================= > ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================