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 ==>
raizes: -1 e 2 ==>
P(n) = A*(-1)^n + B*2^n.
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.
