Re: [obm-l] =?windows-1252?Q?N=E3o_conseguir?=

[Ricardo Bittencourt <ricbit@xxxxxxxxxxxx>]

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