Re: [obm-l] Eureka 01

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Re: [obm-l] Eureka 01

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 ==> 
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.