[obm-l] Re:[obm-l] Questões da Olimpíada de Maio de 1999 (reenviada)
De: [EMAIL PROTECTED] Para: "OBM - Lista" <[EMAIL PROTECTED]> Cópia: Data: Wed, 10 Sep 2003 20:30:11 -0300 Assunto: [obm-l] Questões da Olimpíada de Maio de 1999 (reenviada) Problema 3 A primeira fileira da tabela abaixo se preenche com os números de 1 a 10, em ordem crescente. [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] A segunda fileira se preenche com os números de 1 a 10, em qualquer ordem. Em cada casa da terceira fileira se escreve a soma dos dois números escritos nas casas acima. Existe alguma maneira de preencher a segunda fileira de modo que os algarismos das unidades dos números da terceira fileira sejam todos distintos? Resposta: Não. Seja S(k) = soma dos últimosalgarismos da k-ésima linha (k = 1, 2, 3). Então S(1) = S(2) = 1 + 2 + ... + 9 + 10 = 55. Logo: S(1) = S(2) == 5 (mod 10) Além disso, vale S(3) == S(1) + S(2) (mod 10) == S(3) == 0 (mod 10). Mas, se os algarismos das unidades da 3a. linha forem todos distintos, então teremos também S(3) = 55 == 5 (mod 10) == contradicão. Um abraco, Claudio.
[obm-l] aritmetica
A lista OBM, Tentei de varias formas e nao consegui resolver (montar a solucao), agradeco antecipadamente a atencao. Problema: Para medir o comprimento de uma chacara, duas pessoas percorreram a pe, contando o número de passos que dao. A primeira pessoa da 12 passos mais do que a segunda. Calcular em quilometros o comprimento da chacara, sabendo-se que o passo da primeira pessoa mede 0,77 metros e o da segunda mede 0,80 metros. A resposta do livro: 0,2464 km = 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 =
[obm-l] RE: [obm-l] Questões da Olimpíada de Maio de 1999 (reenviada)
Questão 1: Um número natural de três algarismos é chamado de tricúbico se é igual a soma dos cubos dos seus dígitos. Encontre todos os pares de números consecutivos tais que ambos sejam tricúbicos. 100x + 10y + z = x3 + y3 + z3 e 100x + 10y + (z+1) = x3 + y3 + (z+1)3 Subtraindo uma da outra e desenvolvendo, temos z2 + z=0, logo z = 0 (não pode ser negativo) Logo, x3 + y3 é divisível por 10. Analisando os cubos módulo 10 obtemos que y = x-10 Logo, 100x + 10*(x-10) = x3 + (x-10)^3 x^2 - 13x + 30=0 x = 3 ou x = 10 (não vale) logo, os únicos tricubicos consecutivos são 370 e 371 -Original Message- From: Rodrigo Maranhão [mailto:[EMAIL PROTECTED] Sent: Wednesday, September 10, 2003 8:30 PM To: OBM - Lista Subject: [obm-l] Questões da Olimpíada de Maio de 1999 (reenviada) Estou reenviando o e-mail pq acho q o Server da lista não o encaminhou já q estava com figura. Abaixo vão dois problemas da olimpíada de maio de 1999 que eu gostaria de saber as respostas: Obs: O problema 1 eu resolvi e achei apenas 1 par de tricúbicos consecutivos: 370 e 371. No entanto gostaria de confirmar se a resposta é essa. Problema 1 Um número natural de três algarismos é chamado de tricúbico se é igual a soma dos cubos dos seus dígitos. Encontre todos os pares de números consecutivos tais que ambos sejam tricúbicos. Problema 3 A primeira fileira da tabela abaixo se preenche com os números de 1 a 10, em ordem crescente. [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] A segunda fileira se preenche com os números de 1 a 10, em qualquer ordem. Em cada casa da terceira fileira se escreve a soma dos dois números escritos nas casas acima. Existe alguma maneira de preencher a segunda fileira de modo que os algarismos das unidades dos números da terceira fileira sejam todos distintos? = 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 =
Re: [obm-l] aritmetica
Chame de X o número de passos dados pela 1a pessoa e de Y o de passos da 2a. Então: X = Y + 12 e 0,77X = 0,80Y , já que ambas percorreram toda a extensão da chácara. Esta última eq. é equivalente a 77X= 80Y . Agora resolva o sistema:X=Y+12e 77X= 80Y . Lembre-se de passara resposta para para Km ... Abraço, Frederico. From: Marcelo [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [obm-l] aritmetica Date: Thu, 11 Sep 2003 10:13:12 -0300 A lista OBM, Tentei de varias formas e nao consegui resolver (montar a solucao), agradeco antecipadamente a atencao. Problema: Para medir o comprimento de uma chacara, duas pessoas percorreram a pe, contando o número de passos que dao. A primeira pessoa da 12 passos mais do que a segunda. Calcular em quilometros o comprimento da chacara, sabendo-se que o passo da primeira pessoa mede 0,77 metros e o da segunda mede 0,80 metros. A resposta do livro: 0,2464 km = 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 = _ MSN Messenger: converse com os seus amigos online. http://messenger.msn.com.br = 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 =
Re: [obm-l] aritmetica
A distância medida pelas duas pessoas deve ser a mesma: (x + 12).(077) = x.(0.8) 0.03x = 12.(0.77) x = 308 A 1ª pessoa dá 320 passos e a 2ª 308. Pegando por exemplo a 2ª pessoa: (0.8).308 = 246.4 metros. Que corresponde a 0.2464 Km. - Original Message - From: Marcelo [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Thursday, September 11, 2003 10:13 AM Subject: [obm-l] aritmetica A lista OBM, Tentei de varias formas e nao consegui resolver (montar a solucao), agradeco antecipadamente a atencao. Problema: Para medir o comprimento de uma chacara, duas pessoas percorreram a pe, contando o número de passos que dao. A primeira pessoa da 12 passos mais do que a segunda. Calcular em quilometros o comprimento da chacara, sabendo-se que o passo da primeira pessoa mede 0,77 metros e o da segunda mede 0,80 metros. A resposta do livro: 0,2464 km = 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 = = 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 =
[obm-l] Soma de planetas
Bom dia a todos! Recebi de um aluno o problema MARS + VENUS + SATURN + URANUS = NEPTUNE . Como eu já conheci problemas parecidos iniciei uma resolução considerando que letras diferentes são algarismos diferentes e que nenhum número começa com zero. Conclui que N=1 , S=3ou4ou5 implicando E=0ou3ou6 (considerando a primeira e a última coluna da conta armada), A=7ou6ou5 (terceira coluna), R+U=5ou10ou15(segunda coluna) e M+E+A=9ou19. Combinando as possibilidades cheguei a conclusão que nenhuma se encaixava na solução. Esse problema tem solução ? Agradeço alguma ajuda. Raul = 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 =
Re: [obm-l] aritmetica
Estou admitindo que as duas pessoas deram um numero inteiro de passos para cobrir todo o comprimento da chacara. Sendo n o numero de passos dados pela primeira pessoa, temos que segunda deu n-12 passos. Como ambas percorreram a mesma distância, temos que 0,77n = 0,80 (n-12) = 0,03 n = 0,80 * 12 = n = 320 passos. Logo,o comprimento da chacara eh de 0,77 * 320 = 246,4 m = 0,2464 km. Artur OPEN Internet @ Primeiro provedor do DF com anti-vírus no servidor de e-mails @ = 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 =
Re: [obm-l] UM PROBLEMA INTERESSANTÍSSIMO!
Oi, Johann. Eu que criei esse problema para a Super e não é igual ao problema que você está citando(Banco IMO 91). Lá pedia para provar que uma hora alguém responde sim. Aqui tem que descobrir um número. Foi adaptado sim, mas a adaptação deu trabalho!! Abraços, Ed. --- Johann Peter Gustav Lejeune Dirichlet [EMAIL PROTECTED] wrote: Esse e muito velhoVeja o da OCM e tente o caso geral:prove que, seja la quais foremn os numeros, alguem sempre dirá sim, supondo que os caras sao inteligentes e sinceros --- [EMAIL PROTECTED] escreveu: Olá Turma! Valeu Will pela excelente informação dos links. Muito Obrigado! A e B, os melhores alunos da sua classe, fazem o seguinte jogo: cada um escreve um número natural diferente de zero em uma folha de papel e dá essa folha ao professor. O professor escreve no quadro-negro os números 1994 e 2990, sendo que um deles é a soma dos números de A e B. Então ele pergunta a A: Você sabe o número de B?. A diz não e o professor pergunta a B se ele sabe o número do outro. B também diz não e o professor questiona novamente A, que ainda não sabe a resposta. B, perguntado mais uma vez, dá a resposta correta. Qual é o número de A? Olha Gente! Há décadas, não via um problema tão engenhoso quanto este. (CAMPEÃO!). Sua resolução encontra-se na revista superinteressante. OK! WebMail UNIFOR - http://www.unifor.br = 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 = ___ 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 = __ Do you Yahoo!? Yahoo! SiteBuilder - Free, easy-to-use web site design software http://sitebuilder.yahoo.com = 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 =
Re: [obm-l] Conjunto denso em R
On Wed, Sep 10, 2003 at 05:32:01PM -0300, Artur Costa Steiner wrote: Seja X um espaço topológico e Y um subconjunto de X: Y é denso em X se para todo aberto Z contido em X a interseção de Y com Z é não trivial. O que significa intersecao nao trivial? A definicao que eu ja vi em varios livros, relativa a espacos topologicos, e que Y eh denso em X se o fecho de Y for o proprio X. Eu deveria ter escrito não vazia em vez de não trivial. A sua definição é equivalente à que eu dei. []s, N. = 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 =
[obm-l] Re: [obm-l] UM PROBLEMA INTERESSANTÍSSIMO!
On Thu, Sep 11, 2003 at 12:57:50PM -0300, Johann Peter Gustav Lejeune Dirichlet wrote: Esse e muito velhoVeja o da OCM e tente o caso geral:prove que, seja la quais foremn os numeros, alguem sempre dirá sim, supondo que os caras sao inteligentes e sinceros. Não basta eles serem inteligentes e sinceros: cada um precisa confiar na inteligência e sinceridade do outro, em confiar na confiança que o outro deposita na própria inteligência e sinceridade, e assim por diante. Há muitos problemas que envolvem este tipo de eu sei que você sabe que eu sei que você sabe que eu sei, mas eu não se se você sabe que eu sei que você sabe que eu sei que você sabe que eu sei. Um é o problema das amazonas, que apareceu recentemente nesta lista com um enunciado um pouco diferente. Na ilha das amazonas todas as amazonas são casadas, menos a rainha. Se uma amazona descobre que seu marido a traiu ela o mata a meia-noite. Se uma amazona tem um caso com o marido de outra ela conta isso para todas as amazonas da ilha *menos* para a que foi traída. De fato, há muita traição na ilha: há 1000 amazonas casadas e 395 delas são traídas. Um dia a rainha se cansa disso tudo, chama todas as amazonas e diz: Há traição nesta ilha. O que acontece? []s, N. = 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 =
[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
[obm-l] Um problema muito mais interessante.
Este é uma generalização do problema do banco da IMO no qual me inspirei para montar o tal problema interessantíssimo. Um problema de um verdadeiro campeão, John H. Conway. Há n rapazes sentados em uma mesa circular, cada um com um chapéu em sua cabeça. Um inteiro positivo é escrito em cada chapéu. Nenhum rapaz sabe o número que está no seu chapéu e nem pode vê-lo, mas pode ver os números de todos os demais. O professor escreve em uma lousa k inteiros positivos distintos e anuncia que um dos números é a soma de todos os números escritos nos chapéus. Então pergunta para um dos rapazes: Você sabe a soma dos números?. Se a resposta é não, ele pergunta para o vizinho e assim por diante. Supondo que k é menor ou igual a n (e todas as coisas que o Nicolau citou), prove que, em algum momento, um dirá sim. __ Do you Yahoo!? Yahoo! SiteBuilder - Free, easy-to-use web site design software http://sitebuilder.yahoo.com = 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 =
RE: [obm-l] Contagem
Korshinoi, Tente encontrar a negativa da sua proposicao e subtrair de 3^n. Quantas dessas palavras possuem mais de 2 As adjacentes ? 2 As adjacentes: AA_ _ _ _ _ (n-1) possibilidades. (Posicao do 1º A na casa n-1) 3 As adjacentes: AAA_ _ _ _ _._ (n-2) possibilidades. (Posicao do 1º A na casa n-2) 4 As adjacentes: _ _ _ ..._ (n-3) possibilidades. .. k As adacentes: A.._ (n-k-1) possibilidades n As adjacentes: 1 possibilidade. Total de mais de 2 As adjacentes = (n-1) + (n-2) + (n-3) + + 1 = Soma dos primeiros (n-1) numeros naturais = n(n-1)/2 Portanto, como voce quer excluir essas possibilidades, o numero de palavras sera dado por X = 3^n n(n-1)/2. Se o raciocinio estiver errado, me corrijam, please Leandro. -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of [EMAIL PROTECTED] Sent: Thursday, September 11, 2003 2:06 PM To: [EMAIL PROTECTED] 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
Re: [obm-l] Contagem
seja f(n) := número de palavras de n letras do
alfabeto {A, B, C} sem dois ou maisA's consecutivos
e g(n) :=conta todas aspalavras
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 eque 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...
devemosexpandir (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
Re: [obm-l] Triângulos_(Mr._Crowley)
Estava lendo mensagens antigas e acho que encontrei um erro. O lado AB vale 2sqrt(13). Fabio. Em 4 Sep 2003, [EMAIL PROTECTED] escreveu: Legal cara,ce e o mesmo que foi homenageado pelo Ozzy Osbourne ou colocou este nick como eu fiz o meu? --- Andre Araujo escreveu: AB é a hipotenusa de um triângulo retângulo ABC. A mediana AD mede 7 e a mediana BE mede 4. O comprimento AB é igual a: Pitagoras no triangulo BCE: BC^2+(AC/2)^2=BE^2 Pitagoras no triangulo ACD: (BC/2)^2+AC^2=AD^2 Somando as duas equacoes, temos: (5/4)*(BC^2+AC^2)=16+49, mas BC^2+AC^2=AB^2. Logo: AB^2=4*65/5=AB=2sqrt(15). a)2·sqrt(3) b)5·sqrt(2) c)5·sqrt(3) d)10 e)n.d.a ABC é um triângulo e M é um ponto médio sobre o lado BC, tal que MC=2MB. A razão entre as área dos triângulos ABC e MAC é: Note que a altura relativa ao lado BC(h)do triangulo ABC eh igual a altura relativa ao lado MC do triangulo AMC. Logo: S(ABC)=BC*h/2 S(AMC)=MC*h/2 S(ABC)/S(AMC)=BC/MC=(MC+MB)/MC=(2*MB+MB)/2*MB = 3/2. a)4 b)3 c)2 d)9/4 e)3/2 Grato Mr. Crowley __ Acabe com aquelas janelinhas que pulam na sua tela. AntiPop-up UOL - É grátis! http://antipopup.uol.com.br/ = 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 = -- _ Voce quer um iGMail protegido contra vírus e spams? Clique aqui: http://www.igmailseguro.ig.com.br Ofertas imperdíveis! Link: http://www.americanas.com.br/ig/ = 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 = ___ 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 = -- _ Voce quer um iGMail protegido contra vírus e spams? Clique aqui: http://www.igmailseguro.ig.com.br Ofertas imperdíveis! Link: http://www.americanas.com.br/ig/ Ofertas imperdíveis! = 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 =
Re: [obm-l] Contagem
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 resolverequaçõ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 maisA's consecutivos
e g(n) :=conta todas aspalavras
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 eque 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...
devemosexpandir (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
[obm-l] nicolau
] Quem você conhece ??? Que gostaria de ganhar entre $ 500,00 e $ 2.500,00 extra por mês, sem interferir em sua atividade principal ??? Trabalhando de casa ou escritório usando seu computador. Informações no site www.empreendimentointernacional.kit.net Att www.empreendimentointernacional.kit.net .
