Re: [obm-l] Não conseguir

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

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 ricbit@700km.com.br 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
> ricbit@700km.com.br           "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
=========================================================================