[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Contagem
Uma boa ideia e ver o grafo a seguir:
V={A,B,C}
A={AB,AC,BB,CC}
Com isto da pra contar quantos caminhos de
tamanho n existem.depois eu envio algo a mais...
--- "Marcio Afonso A. Cohen"
<marciocohen@superig.com.br> 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: obm-l@mat.puc-rio.br
> 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: Korshinoi@aol.com
> To: obm-l@mat.puc-rio.br
> 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
=========================================================================