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