[obm-l] Sequencias de A's, B's, C's

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 27.10.04 22:25, jorgeluis@edu.unifor.br at jorgeluis@edu.unifor.br wrote:
> 
> A propósito, usando as letras A, B e C podemos formar 3^n "palavras" de n
> letras. Quantas dessas palavras não possuem dois ou mais A's adjacentes?
> 
Seja f(n) o numero de palavras de n letras nas condicoes do enunciado.

Eh facil ver que f(1) = 3, f(2) = 8 e f(3) = 22.

Seja n >= 3 e consideremos uma palavra de n-1 letras sem A's adjacentes.
Vamos contar de quantas formas podemos escolher a n-esima letra.

Existem 4 casos possiveis:

1) a (n-1)-esima letra eh B ==>
a n-esima letra pode ser A, B ou C ==> 3 possibilidades

2) a (n-1)-esima letra eh C ==>
a n-esima letra pode ser A, B ou C ==> 3 possibilidades

3) as (n-2) e (n-1)-esimas letras sao BA ==>
a n-esima letra pode ser B ou C ==> 2 possibilidades

4) as (n-2) e (n-1)-esimas letras sao CA ==>
a n-esima letra pode ser B ou C ==> 2 possibilidades

Casos (1) e (2) originam 6*f(n-2) palavras de n letras.
Casos (3) e (4) originam 4*f(n-3) palavras de n letras

Logo, f(n) = 6*f(n-2) + 4*f(n-3) ==>

Eq. caracteristica: x^3 - 6x - 4 = 0 ==>
raizes: -2, 1+raiz(3) e 1-raiz(3)

f(n) = A*(1+raiz(3))^n + B*(1-raiz(3))^n + C*(-2)^n

Substituindo n = 1, 2 e 3, usando os valores correspondentes de f(n) e
resolvendo o sistema resultante, achamos:
A = (3+2*raiz(3))/6; B = (3-2*raiz(3))/6; C = 0

Ou seja:
f(n) = (1/6)*((3+2*raiz(3))*(1+raiz(3))^n + (3-2*raiz(3))*(1-raiz(3))^n)


[]s,
Claudio.


=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================