on 27.10.04 22:25, [EMAIL PROTECTED] at [EMAIL PROTECTED] 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 =========================================================================