Este problema ja caiu numa olimpiada bulgara.Depois eu confiro a resposta mas esta coisa de autovalores e melhor com algumas coisas que ninguem aprende sobre o poder da algebra linear...
Claudio Buffara <claudio.buffara@terra.com.br> wrote:
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
=========================================================================