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.