Oi, Nicolau: Eu calculei o no. de maneiras de se cobrir um tabuleiro 3 x 2n com dominos 2x1 e achei a recorrencia:
f(n) = 3*f(n-1) + g(n-1) g(n) = 2*f(n-1) + g(n-1) f(1) = 3, g(1) = 2 onde f(n) = no. desejado e g(n) = no. de maneiras de se chegar a casa 2n com 2 dominos deitados. Eliminando g(n): f(n) = 4*f(n-1) - f(n-2); f(1) = 3; f(2) = 11. f(n) = 3, 11, 41, 153, 571, 2131, ... Resolvendo eu achei a formula explicita para f(n): f(n) = (1/6)*[(3+raiz(3))*(2+raiz(3))^n + (3-raiz(3))*(2-raiz(3))^n] Minha duvida: Existe alguma razao para os autovalores (2+ou-raiz(3)) serem os mesmos que no caso do pilar ou foi soh coincidencia? Qual o papel (ou interpretacao) dos autovalores nesse tipo de problema? Um abraco, Claudio. on 05.10.03 23:12, Claudio Buffara at [EMAIL PROTECTED] wrote: > on 04.10.03 11:44, Nicolau C. Saldanha at [EMAIL PROTECTED] > wrote: > >> On Thu, Oct 02, 2003 at 09:11:23PM -0300, [EMAIL PROTECTED] wrote: >>> De quantas maneiras pode ser constru�do um pilar 2x2xn com tijolos 2x1x1? >> >> Calculei os primeiros termos desta seq��ncia: >> >> 1,2,9,32,121,450,1681,6272,23409,87362,326041,1216800,... >> >> e procurei na enciclop�dia de seq��ncias de inteiros: >> >> http://www.research.att.com/~njas/sequences/Seis.html >> >> A enciclop�dia conhece a seq��ncia, ela se chama A006253. >> A enciclop�dia tamb�m indica que este problema est� no Concrete Mathematics, >> de Graham, Knuth e Patashnik, p�gina 360. >> A p�gina tamb�m d� uma f�rmula bem simples que eu n�o vou copiar >> (para que voc�s possam tentar obter sozinhos >> e tb para que olhem as refer�ncias). >> > > Oi, Nicolau: > > Depois de umas 5 tentativas frustradas (onde eu invariavelmente esquecia de > levar em conta alguma alternativa), finalmente consegui descobrir a relacao > de recorrencia para esse problema. > > Sejam: > f(n) = no. de maneiras de se construir um pilar de altura n; > g(n) = no. de maneiras de se chegar ao n-esimo andar com 2 tijolos colocados > verticalmente (apoiados no (n-2)-esimo andar) e lado a lado. > > Por enumeracao direta obtemos: > f(1) = 2 e f(2) = 9 > g(1) = 0 e g(2) = 4 > > As relacoes de recorrencia sao: > g(n) = 4*f(n-2) + g(n-1) > f(n) = 2*f(n-1) + f(n-2) + g(n) > > Justificativa: > g(n): Se temos um plateau no (n-2)-esimo andar, entao podemos colocar 2 > tijolos verticalmente e lado a lado para chegar ao n-esimo andar de 4 > maneiras (em cada uma das 4 faces do pilar). Esse eh o termo 4*f(n-2) > Se ja existem 2 tijolos verticais no (n-1)-esimo andar (portanto, apoiados > no (n-3)-esimo andar), entao, soh teremos 1 maneira de apoiar tijolos > verticais no (n-2)-esimo andar. Esse eh o termo g(n-1). > > f(n): Se temos um plateau no (n-1)-esimo andar, entao podemos colocar 2 > tijolos horizontais de 2 maneiras para completar o n-esimo andar (norte-sul > ou leste-oeste). Esse eh o termo 2*f(n-1). > Se temos um plateau no (n-2)-esimo andar, entao podemos colocar 4 tijolos > verticais e chegar ao n-esimo andar. Esse eh o termo f(n-2) > Se temos dois tijolos verticais lado a lado no n-esimo andar (portanto, > apoiados no (n-2)-esimo andar), soh teremos uma maneira de colocar o tijolo > restante e completar o n-esimo andar. Esse eh o termo g(n). > > ***** > > Calculando, obtemos: > n g(n) f(n) > 1 0 2 > 2 4 9 > 3 12 32 > 4 48 121 > 5 176 450 > 6 660 1681 > 7 2460 6272 > 8 9184 23409 > 9 34272 87362 > 10 127908 326041 > > ***** > > Pondo X(n) = (g(n),f(n),f(n-1))^transposto, a recorrencia se torna: > X(n) = P*X(n-1) > onde P eh a matriz: > 1 0 4 > 1 2 5 > 0 1 0 > cujos autovalores sao -1, 2+raiz(3) e 2-raiz(3). > > Supondo uma solucao da forma: > f(n) = a*(-1)^(n-1) + b*(2+raiz(3))^(n-1) + c*(2-raiz(3))^(n-1) > e > resolvendo o sistema resultante pela substituicao de n = 1, 2 e 3, eu achei > a expressao: > > f(n) = (-1)^n/3 + [(2+raiz(3))^(n+1) + (2-raiz(3))^(n+1)]/6 > > ***** > > De fato, o problema acabou sendo mais sutil do que eu pensava inicialmente. > Agora eu entendo o que voce disse sobre a dificuldade de se resolver o caso > de um paralelepipedo m x n x p. > > > Um abraco, > Claudio. > ========================================================================= 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 =========================================================================
