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