Re: [obm-l] Eureka 01

[Faelccmm@xxxxxxx]

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:


> on 16.06.04 00:20, Faelccmm@aol.com at Faelccmm@aol.com wrote:
>
> > Ola pessoal, 
> >
> >
> > Os vertices 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 
>
> Oi, Fael:
>
> Uma ideia eh comecar com poligonos pequenos. Assim, seja P(n) = numero de formas de se pintar um n-gono regular nas condicoes do enunciado.
>
> Pro triangulo, nao tem muito misterio:
> P(3) = 3*2*1 = 6
>
> Calculo de P(4):
> Seja o quadrado ABCD. Imagine que pintamos os vertices A e B com as cores 1 e 2, respectivamente.
> Se o vertice C tiver a cor 1, entao D poderah ser 2 ou 3.
> Se o vertice C tiver a cor 3, entao D soh poderah ser 2.
> Obviamente, C nao poderah ter a cor 2.
> Logo, fixadas as cores de A e B, teremos 3 possibilidades para as cores dos outros dois vertices.
> Como podemos escolher as cores de A e B de 3*2 maneiras, o numero total de pinturas distintas dos vertices do quadrado eh 3*2*3 = 18.
> Ou seja, P(4) = 18.
>
> A partir daqui, a melhor ideia que me ocorre eh tentar achar alguma relacao de recorrencia.
>
> Considere um n-gono regular e tres vertices adjacentes dele - A, B e C.
> Ao pintar seus vertices nas condicoes do enunciado (o que pode ser feito de P(n) maneiras distintas), teremos exatamente dois casos:
>
> 1) A e C tem cores diferentes.
> Nesse caso, a cor de B eh unicamente determinada e podemos considerar que esta pintura originou-se de um (n-1)-gono, pintado de acordo com o enunciado, e no qual se inseriu o n-esimo vertice (B) entre dois vertices existentes (A e C -que tinham cores distintas).
> Isso pode acontecer de P(n-1) maneiras diferentes.
>
> 2) A e C tem cores iguais.
> Nesse caso, podemos considerar que este n-gono originou-se de um (n-2)-gono regular, pintado de acordo com o enunciado, onde um vertice (A) dividiu-se em dois (A e C - da mesma cor), resultando em n-1 vertices, e inseriu-se um vertice (B - de cor diferente) entre os dois (total = n vertices). A cor deste ultimo vertice pode ser escolhida de 2 maneiras distintas.
> Logo, isso pode acontecer de 2*P(n-2) maneiras diferentes.
>
> 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.