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