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

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

On Sun, Jun 08, 2003 at 11:55:47AM -0300, fnicks wrote:
> Olá pessoal ,
> 
> 
> Poderiam me ajudar nos problemas abaixo ?
> 
> 2)Com 23 movimentos , de quantas maneiras podemos sair de 1 e chegar ao 2 , 
> na disposição abaixo ?
> 
> 
> 
> 
> 
> 1--------2-------3---------4
> -        -       -         -
> -        -       -         -
> -        -       -         -
> 5--------6-------7---------8
> 
> 
> 
> Nota : observe que há apenas ligações horizontais e verticais e que podemos 
> retornar .( o 5  está na mesma  vertical de 1 , o 6  abaixo  de 2 , o 7 
> abaixo de 3 , o 8 abaixo de 4 )

Bem, antes de mais nada observe que o diagrama pode ser pintado com
branco e preto, aqui no texto com 0 e X, assim:

 0--------X-------0---------X
 -        -       -         -
 -        -       -         -
 -        -       -         -
 X--------0-------X---------0

donde, a partir de 1 (pintado de branco) em um número par de jogadas
sempre estamos em outro branco e em um número ímpar sempre em um preto.
23 é ímpar e o 2 é preto, então a resposta não é zero.
Basta portanto contar o número de caminhos da 1a para a 2a coluna.

Se o número de caminhos de comprimento n a partir de 1 para chegar
em cada coluna é dado por (x1,x2,x3,x4) então o número de caminhos
de comprimento n+1 é dado por (x1+x2,x1+x2+x3,x2+x3+x4,x3+x4)
bastando para ver isso considerar as formas de prolongar cada caminho.

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)

Se você tiver um computador e um programa tipo o maple ou o mathematica
a mào o problema acabou, basta fazer esta conta. Caso contrário,
use lápis, papel e muita disposição para calcular A^2, A^3 = A^2*A,
A^5 = A^3*A^2, A^10 = A^5*A^5, A^11 = A^10*A, A^22 = A^11*A^11, A^23 = A^22*A.
Usando o maple, A^23 vale:

             [567474769     918170280     918141623    567428401]
             [                                                  ]
             [918170280    1485616392    1485598681    918141623]
             [                                                  ]
             [918141623    1485598681    1485616392    918170280]
             [                                                  ]
             [567428401     918141623     918170280    567474769]

e o número que você quer é 918170280.

[]s, N. 

Mas vamos supor que este
*não* é o caso e vamos continuar:



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