Re: [obm-l] Contagem

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Re: [obm-l] Contagem

on 09.10.03 14:26, andr� luiz rodrigues chaves at andrezinho1964@terra.com.br wrote:

> Uma pessoa possui tr�s �culos: um azul, um preto e o outro cinza. Ela sempre usa um �culos em cada dia do m�s. Num m�s de 30 dias, de quantas maneiras diferentes ela poder� usar os referidos �culos de modo que n�o haja repeti��o de cor em dias consecutivos e que o �culos cinza seja usado nos dias 1 e 30.

Aqui vai a minha tentativa. Criticas (construtivas, por favor!) serao bem vindas.

Sejam:
F(n) = numero de maneiras de escolher as cores dos n dias, sendo que no dia 1 e no dia n a pessoa tem que usar a mesma cor.

G(n) = numero de maneiras de escolher as cores dos n dias, sendo que no dia 1 e no dia n a pessoa tem que usar cores diferentes.

(em ambos os casos, uma mesma cor nao pode ser usada em dias consecutivos).

Queremos F(30).

Por enumeracao direta obtemos:
F(1) = 1, F(2) = 0, F(3) = 2, F(4) = 2.

Alem disso, temos as relacoes:
F(n) = 2*(F(n-2) + G(n-2))
3*F(n) + 6*G(n) = 3*2^(n-1)

Eliminando G(n):
F(n) = F(n-2) + 2^(n-3)

Logo:
F(4) - F(2) = 2^1
F(6) - F(4) = 2^3
F(8) - F(6) = 2^5
....
F(28) - F(26) = 2^25
F(30) - F(28) = 2^27

Somando tudo e cancelando:
F(30) - F(2) = 2*(1 + 4 + 4^2 + ... + 4^13) ==>
F(30) = 2*(4^14 - 1)/(4 - 1) ==>
F(30) = (2/3)*(4^14 - 1) = 178956970.

Um abraco,
Claudio.