[obm-l] Tabuleiro 3 x 2n com dominos 2x1
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 31232 448 121 5 176 450 6 660 1681 7 2460 6272 8 9184 23409 9 34272 87362 10127908326041 * 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 =
Re: [obm-l] Tabuleiro 3 x 2n com dominos 2x1
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 [EMAIL PROTECTED] wrote: Oi, Nicolau:Eu calculei o no. de maneiras de se cobrir um tabuleiro 3 x 2n com dominos2x1 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) = 2onde f(n) = no. desejado e g(n) = no. de maneiras de se chegar a casa 2n com2 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)) seremos mesmos que no caso do pilar ou foi soh coincidencia? Qual o papel (ouinterpretacao) 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 emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html=Yahoo! Mail - o melhor webmail do Brasil. Saiba mais!
