Uma boa ideia e ver o grafo a seguir: V={A,B,C} A={AB,AC,BB,CC,BC} Com isto da pra contar quantos caminhos de tamanho n existem.depois eu envio algo a mais... --- "Marcio Afonso A. Cohen" <[EMAIL PROTECTED]> escreveu: > Seguem alguns comentarios rapidos sobre esse > problema.. Eh provavel que eu tenha errado as > contas (nao conferi e fiz meio rapido), mas > desse jeito foi bom que a resposta ficou > simpatica.. > Chame de x(n) as palavras de n letras sem dois > A's adjacentes. > Quantas palavras x(n+2) existem? > Se a primeira letra for A, há duas opções > para a segunda letra (B ou C) e a partir daí > temos x(n) opções. > Caso contrário, há duas opções para a > primeira letra (B ou C) e a partir daí temos > x(n+1) opções. > Logo, x(n+2) = 2x(n+1) + 2x(n) (*) > Usar funções geratrizes em geral não é uma > boa técnica para resolver equações lineares de > coeficientes constantes pq nesse caso tem uma > teoria mais prática, muito parecida com a que > voce usa para resolver EDOs.. > Sem maiores explicacoes sobre a teoria (qq > coisa, de uma lida na Eureka ou mande um email > que eu dou mais detalhes): > Solucoes da forma t^n: t^2 - 2t - 2 = 0 > => t = 1 +- sqrt(3), logo x(n) = a(1+sqrt(3))^n > + b(1-sqrt(3))^n eh solucao de (*) qq que sejam > a,b. > No nosso caso porém, x(1)=3, x(2)=8 (donde > a recorrencia da x(0) = 1) e portanto a+b=1, > (a+b) + (a-b)sqrt(3) = 3 e então > a = (2+sqrt(3))/2sqrt(3) = > (1+sqrt(3))^2/8sqrt(3), b = > (-2+sqrt(3))/2sqrt(3) = -(1-sqrt(3))^2/8sqrt(3) > Logo, x(n) = [(1+sqrt(3))^(n+2) - > (1-sqrt(3))^(n+2)]/8sqrt(3) > Mais legal ainda é que, como > (1-sqrt(3))^(n+2) / 8sqrt(3) eh quase sempre > muito pequeno, e x(n) eh inteiro, voce pode > concluir que: > n par: x(n) = Piso {(1+sqrt(3))^(n+2)/8sqrt(3)} > n impar: x(n) = Teto > {(1+sqrt(3))^(n+2)/8sqrt(3)} > ----- Original Message ----- > From: Domingos Jr. > To: [EMAIL PROTECTED] > Sent: Thursday, September 11, 2003 8:47 PM > Subject: Re: [obm-l] Contagem > > > seja f(n) := número de palavras de n letras > do alfabeto {A, B, C} sem dois ou mais A's > consecutivos > e g(n) := conta todas as palavras contadas > por f(n) que terminam em A. > f(1) = 3, g(1) = 1 > f(n + 1) = 3f(n) - g(n) > [a idéia: uma palavra de n+1 letras deve > ser formada por uma palavra de n letras mais > uma letra, essa letra pode ser A, B, C e a > palavra anterior a ela não pode ter A's > consecutivos, no entanto se a palavra de > tamanho n termina em A, não podemos colocar A > como última letra, logo descontamos g(n)] > g(n + 1) = f(n) - g(n) > [pegamos uma palavra de n letras sem A's > consecutivos e que NÃO termina em A e > concatenamos um A] > > > agora vamos tentar resolver essas > recorrências! > f(n) = g(n+1) + g(n) => > f(n + 1) = g(n + 2) + g(n + 1) > mas > f(n + 1) = 3f(n) - g(n) = 3g(n + 1) + 2g(n) > logo > > 3g(n + 1) + 2g(n) = g(n + 2) + g(n + 1) > g(n + 2) = 2[g(n + 1) + g(n)] = 2f(n) > f(n + 2) = g(n + 3) + g(n + 2) = 2f(n + 1) + > 2f(n) = 2[f(n+1) + f(n)] > > > a recorrência passa a ser: > f(1) = 3, f(2) = 8 > f(n + 2) = 2[f(n+1) + f(n)], n >= 1 > > os primeiros valores são 3, 8, 22, 60, 164, > ... > > vamos obter a função geradora dessa nossa f. > seja A(x) = soma{i=1..oo} f(i)*x^i > f(n + 2) = 2[f(n+1) + f(n)] => > soma{i=1..oo} f(n + 2) = soma{i=1..oo} > 2[f(n+1) + f(n)] > > temos: > soma{i=1..oo} f(n + 2) = f(3)x + f(4)x² + ... > = [A(x) - f(1)x - f(2)x²]/x² = [A(x) -3x - > 8x²]/x² > soma{i=1..oo} f(n + 1) = f(2)x + f(3)x² + ... > = [A(x) - f(1)x]/x = [A(x) - 3x]/x > > logo: > [A(x) -3x - 8x²]/x² = 2{[A(x) - 3x]/x + A(x)} > A(x) -3x - 8x² = 2{xA(x) - 3x² + x²A(x)} > A(x) (2x² + 2x - 1) = (-2x² - 3x) > A(x) = (-2x² - 3x)/(2x² + 2x - 1) = -1 - > (x+1)(2x² + 2x - 1) > > > precisamos agora calcular o coeficiente de > x^n na série que define A(x), fazer isso é um > pouco trabalhoso e é bem técnico... o livro do > Herbert Wilf, generatingfunctionology calcula o > falor de fib(n), a sequência de Fibonacci... > > devemos expandir (x+1)/(1 - 2x - 2x²) em > "partial fractions" (não sei uma boa tradução). > > infelizmente estou apanhando pra fazer essa > expansão, fico te devendo! > > um lugar legal pra ver que vc acertou o > problema é: > http://www.research.att.com/~njas/sequences/ > que tem um banco de dados grande de > seqüências inteiras, procure a sequência 3, 8, > 22, 60, 164 pra vc ver que legal! > > [ ]'s > > ----- Original Message ----- > From: [EMAIL PROTECTED] > To: [EMAIL PROTECTED] > Sent: Thursday, September 11, 2003 6:05 PM > Subject: [obm-l] Contagem > > > 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?? > Esse exercício foi extraído do livro > Problem-solving strategies, de Arthur Engel. > Gostaria de ver outra solução, pois, a > expressão final da minha solução está muito > estranha...risos...eu diria ...desengonçada. Se > alguém fizer eu agradeço. > Korshinoi >
_______________________________________________________________________ Desafio AntiZona: participe do jogo de perguntas e respostas que vai dar um Renault Clio, computadores, câmeras digitais, videogames e muito mais! www.cade.com.br/antizona ========================================================================= 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 =========================================================================