[obm-l] Re: [obm-l] Re: [obm-l] Combinatória

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

On Mon, Jun 09, 2003 at 09:48:20AM -0300, Nicolau C. Saldanha wrote:
> Assim, o número de caminhos de tamanho 23 de 1 a 2 é a entrada (1,2)
> de A^23 onde A é a matriz abaixo:
> 
>  (1 1 0 0)
>  (1 1 1 0)
>  (0 1 1 1)
>  (0 0 1 1)

Não sei se vocês gostaram do final da solução mas eu não gostei.
Seja X a matriz abaixo:

 (1  0  0  1)
 (0  1  1  0)
 (0  1 -1  0)
 (1  0  0 -1)

A idéia de considerar X vem da simetria do problema:
vetores pares (a,b,b,a) e ímpares (a,b,-b,-a) são levados
em vetores pares e ímpares, respectivamente.
Temos X^(-1) = 1/2 X e a conjugada B = X^(-1)AX é igual a

 (1 1 0 0)
 (1 2 0 0)
 (0 0 0 1)
 (0 0 1 1)

que tem na diagonal dois blocos B1 e B2.
Para calcular B^23 basta portanto calcular B1^23 e B2^23
e depois é fácil recuperar A^23.

Mas B1 e B2 são velhas conhecidas nossas:
B2 é a matriz que calcula a seq de Fibonacci (rodada)
e B1 é o quadrado dela. Assim, B1^n e B2^n são respectivamente

 ( f(2n-1)   f(2n)  )
 (  f(2n)   f(2n+1) )

 ( f(n-1)  f(n)  )
 (  f(n)  f(n+1) )

onde f(0) = 0, f(1) = f(2) = 1, f(n+1) = f(n) + f(n-1). Assim A^n é
X B^n X^(-1), ou seja, 2 A^n é a matriz abaixo:

 (  f(2n-1) + f(n+1)   f(2n) + f(n)        f(2n) - f(n)    f(2n-1) - f(n+1) )
 (   f(2n) + f(n)     f(2n+1) + f(n-1)   f(2n+1) - f(n-1)    f(2n) - f(n)   )
 (   f(2n) - f(n)     f(2n+1) - f(n-1)   f(2n+1) + f(n-1)    f(2n) + f(n)   )
 (  f(2n-1) - f(n+1)   f(2n) - f(n)        f(2n) + f(n)    f(2n-1) + f(n+1) )

e o número que você quer é (f(46) + f(23))/2 = 918170280.

[]s, N.


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