[obm-l] Tabuleiro 3 x 2n com dominos 2x1

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

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 claudio.buffara@terra.com.br wrote:

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