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 =========================================================================
