[obm-l] Problema da Eureka-retorno

[Faelccmm@xxxxxxx]

Ola Claudio e demais colegas,

Estou retornando a mensagem, pois andei pensando:
- Sera que o problema nao admite outra solucao ? Pois equacoes de recorrencia eh um assunto tratado na Eureka 09 e o problema enviado por mim esta na Eureka 01. Creio que os responsaveis por esta revista tratam-na de forma organizada, logo deve haver um padrao de resposta envolvendo conceitos mais simples, por se tratar da primeira Eureka. Ou os problemas da Eureka estao dispersos de forma caotica e desorganizada ? Se os criadores da revista esperassem um padrao de resposta para aquela questao (Eureka 01) envolvendo equacoes de recorrencia (Eureka 09) entao qual a finalidade de colocar este artigo sobre equacoes de recorrencia numa edicao posterior. Isso eh a mesma coisa que alguem escrever um livro que tenha algumas questoes de trigonometria e passar a teoria so no segundo volume ... estranho, nao ?

De qualquer forma, aqui vai o problema:


Os vértices de um decagono regular convexo ABC...J devem ser coloridos usando-se apenas as cores verde, amarela e azul. De quantos modos isso pode ser feito se vertices adjacentes nao podem receber a mesma cor ? 

a)1022              b)1024              c)1026              d)1524              e)1536



Em uma mensagem de 18/6/2004 14:11:39 Hora padrão leste da Am. Sul, claudio.buffara@terra.com.br escreveu:


> Sua duvida eh sobre equacoes de recorrencia. De uma olhada na Eureka 09.
>
> De qualquer forma, a ideia eh a seguinte:
> Dada a recorrencia: P(n) = P(n-1) + 2*P(n-2), parece ser bem razoavel que procuremos solucoes da forma P(n) = x^n, para algum x real.
>
> Por que isso eh razoavel?
> Porque se tivessemos, por exemplo, a recorrencia de 1a. ordem (ou seja, P(n) expresso apenas em funcao de P(n-1)) P(n) = k*P(n-1), a solucao seria obviamente da forma P(n) = A*k^n. Logo, talvez valha a pena tentar uma solucao da mesma forma para uma recorrencia de 2o. ordem onde P(n) eh expresso como funcao de P(n-1) e P(n-2))
>
> Se uma tal solucao existir, entao vai valer x^n = x^(n-1) + 2*x^(n-2), certo?
> Dividindo por x^(n-2) e passando tudo pro lado esquerdo, voce fica com:
> x^2 - x - 2 = 0.
> Isso significa que se existir x tal que P(n) = x^n, ele soh poderah ser -1 ou 2.
>
> Jah que temos dois valores possiveis para x, que tal testar uma combinacao linear deles, justamente da forma P(n) = A*(-1)^n + B*2^n, onde A e B sao parametros reais a serem determinados. 
> Por que uma combinacao linear?
> Porque se (-1)^n e 2^n satisfazem a recorrencia P(n) = P(n-1) + 2*P(n-2), entao qualquer combinacao linear deles tambem vai satisfazer. Pode conferir.
>
> E como determinar A e B? 
> Simples: a partir das condicoes iniciais: P(3) = 6 e P(4) = 18.
> Resolvendo o sisteminha resultante, achamos A = 2 e B = 1, donde:
> P(n) = 2*(-1)^n + 2^n.
>
> Repare que a argumentacao acima nao provou nada. Apenas apresentou uma forma plausivel de se "adivinhar" a solucao da equacao de recorrencia. No entanto, pode-se provar que esta eh "a" solucao, ou seja, que a solucao achada acima eh unica.
>
> []s,
> Claudio.
>
> on 18.06.04 13:20, Faelccmm@aol.com at Faelccmm@aol.com wrote:
>
> > Claudio, 
> >
> > Algumas de minhas duvidas estao no corpo de sua resolucao. 
> >
> >
> >
> > Em uma mensagem de 16/6/2004 09:46:16 Hora padrão leste da Am. Sul, claudio.buffara@terra.com.br escreveu: 
> >
> > [...]
> >
> > Assim, temos a recorrencia: P(n) = P(n-1) + 2*P(n-2). 
> > Juntamente com P(3) = 6 e P(4) = 18, podemos achar P(n) para qualquer n. 
> >
> > Equacao caracteristica: x^2 - x - 2 = 0 (De onde voce tirou esta equacao caracteristica ? *Equacao caracteristica* eh um conceito ou uma expressao utilizada por voce ?) ==> 
> > raizes: -1  e  2 ==> 
> > P(n) = A*(-1)^n + B*2^n. (Por que aqui voce fez A*[raiz_1]*(-1)^n + B*[raiz_2]^n ? Quem sao estes A´s e B´s ? Qual a logica desta equacao ? 
> >
> > P(3) = -A + 8B = 6 
> > P(4) = A + 16B = 18 ==> A = 2  e  B = 1 ==> 
> >
> > P(n) = 2*(-1)^n + 2^n ==> 
> >
> > P(10) = 1026 ==> alternativa (c). 
> >
> > []s, 
> > Claudio.