[obm-l] Pilar 2x2xn com tijolos 2x1x1

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 04.10.03 11:44, Nicolau C. Saldanha at nicolau@sucuri.mat.puc-rio.br
wrote:

> On Thu, Oct 02, 2003 at 09:11:23PM -0300, jorgeluis@edu.unifor.br 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
=========================================================================