Oi, Fael:
Este problema certamente deve admitir outra solucao (mas nao outra resposta!). Recorrencia foi apenas a ideia que me ocorreu para resolve-lo.
Nao me parece haver relacao alguma entre os temas dos artigos expositorios num dado numero da Eureka e as tecnicas que devem ser utilizadas para se resolver os problemas lah propostos. As Eurekas nao sao livros-texto. Num dado numero voce pode encontrar um artigo sobre geometria, outro sobre teoria dos numeros e um problema sobre polinomios, por exemplo, sem que haja nenhum artigo tratando desse assunto naquele numero ou em qualuer numero anterior. De fato, tenho quase certeza de nunca foi publicado na Eureka algum artigo sobre polinomios, apesar do Shine ter escrito um para uma semana olimpica ha algum tempo atras (veja o site da obm).
[]s,
Claudio.
| De: |
owner-obm-l@mat.puc-rio.br |
| Para: |
obm-l@mat.puc-rio.br |
| Data: |
Mon, 28 Jun 2004 00:04:24 EDT |
| Assunto: |
[obm-l] Problema da Eureka-retorno |
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.