[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] Eureka 01



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.