Re: [obm-l] Dúvidas:_Algoritimo
5 elementos? pra cada elemento você compara com todos os outros, uma implementação grosseira gastaria 20 comparações, o que não é nada se isso for rodar num computador :P você pode criar um array a[n], tal que a[n] = 1 se a[n] esta no conjunto, a[n] = 0 caso contrário, o que da O(1) para ver se um elemento ja está no seu conjunto e O(1) para atualizar, mas gastando bastante espaço dependendo dos valores possíveis de cada elemento. senão você pode implementar uma arvore de busca binária, o que daria O(log(5)) para fazer a query e O(log(5)) para atualizar, mas gastando menos espaço --- Marcos Eike [EMAIL PROTECTED] escreveu: Pessoal, eu estou querendo criar um algoritmo para analisar cada entrada de um numero, num array de 5 elementos, comparando com os elementos anteriores. Sendo que com isso eu consiga assegurar que esse array nao tera elementos repetidos.. Basta me mostrar um possivel caminho... dum jeito mais optimizado possivel Obrigado! __ Yahoo! Messenger - Fale com seus amigos online. Instale agora! http://br.download.yahoo.com/messenger/ = 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] exercícios
on 14.05.04 11:53, biper at [EMAIL PROTECTED] wrote: 2)Encontre as soluções inteiras de. x^3 - y^3 = 999 A primeira observacao eh que se (a,b) eh solucao, entao (-b,-a) tambem eh. Logo, podemos nos limitar ao caso em que x 0. Caso 1: x y 0. A equacao pode ser re-escrita como: (x - y)(x^2 + xy + y^2) = 3^3*37 Temos 4 sub-casos a considerar: 1) x - y = 1 e x^2 + xy + y^2 = 999 2) x - y = 3 e x^2 + xy + y^2 = 333 3) x - y = 9 e x^2 + xy + y^2 = 111 4) x - y = 27 e x^2 + xy + y^2 = 37 Repare que cada um desses sub-casos se reduz a uma equacao do 2o. grau, da qual buscamos raizes inteiras. As unicas solucoes obtidas correspondem aos casos 2 e 3. Sao, respectivamente, (12,9) e (10,1). Da observacao inicial obtemos as solucoes (-9,-12) e (-1,-10). Caso 2: x 0 y. Nesse caso, fazendo z = -y 0, obtemos a equacao: x^3 + z^3 = 999 == (x + z)*(x^2 - xz + z^2) = 3^3*37 Novamente, temos 4 sub-casos a considerar: 1) x + z = 1 e x^2 - xz + z^2 = 999 2) x + z = 3 e x^2 - xz + z^2 = 333 3) x + z = 9 e x^2 - xz + z^2 = 111 4) x + z = 27 e x^2 - xz + z^2 = 37 Nenhuma das 4 equacoes do 2o. grau resultantes tem raizes inteiras (o que eh mais ou menos obvio, jah que x e z sao positivos) Logo, as unicas solucoes sao: (12,9), (-9,-12), (10,1) e (-1,-10). []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 =
[obm-l] Re:[obm-l] RE: [obm-l] área
A área do seg. circ. corresponde à área do setor circular menos a àrea do triangulo isosceles formado. I) Area do setor 360 - pi.1^2 50 - S(1) S(1)=5pi/36 II) Area do tring. O triagulo tem lados 1 1 e angulo entre estes lados de 50°, logo S(2)=1.1.sen(50°)/2 III) Area do seg. circ. Portanto a àrea do segmento circular é S(1)-S(2) =5.pi/36-sen(50°)/2 =0.4361-0.3830=0.0531 Resposta b) -- Início da mensagem original --- De: [EMAIL PROTECTED] Para: [EMAIL PROTECTED] Cc: Data: Fri, 14 May 2004 22:34:06 -0400 Assunto: RE: [obm-l] área Ainda ñ consegui matar aquela segunda mais tõ tentando enquanto a origem, tb acho que foi de alguma obm só ñ sei o ano, se alguém descobrir me avisem. Hoje quando estava voltando para casa um amigo me propôs uma questão e fiquei meio em dúvida, aí vai: Seja S a área de um segmento circular de 50 graus, numa circunferência de raio unitário,pode-se afirmar que: a)0,02S0,04 b)0,04S0,09 c)0,09S0,70 d)0,25S0,30 S360 = 3.14 S50 = 0.44 opcao (c) Essa ñ seria a área do setor circular?,ele quer do segmento circular Um abraço Felipe Santana ___ _ _ Express yourself with the new version of MSN Messenger! Download today - it's FREE! http://messenger.msn.click- url.com/go/onm00200471ave/direct/01/ === = = 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 === = = ___ ___ 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 === == Atenciosamente, Engenharia Elétrica - UNESP Ilha Solteira Osvaldo Mello Sponquiado Usuário de GNU/Linux __ 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 =
[obm-l] Re:[obm-l] Re:[obm-l] RE: [obm-l] área
-- Início da mensagem original --- De: [EMAIL PROTECTED] Para: quot;obm-lquot; [EMAIL PROTECTED] Cc: Data: Sat, 15 May 2004 11:00:14 -0300 Assunto: [obm-l] Re:[obm-l] RE: [obm-l] área A área do seg. circ. corresponde à área do setor circular menos a àrea do triangulo isosceles formado. I) Area do setor 360 - pi.1^2 50 - S(1) S(1)=5pi/36 II) Area do tring. O triagulo tem lados 1 1 e angulo entre estes lados de 50°, logo S(2)=1.1.sen(50°)/2 III) Area do seg. circ. Portanto a àrea do segmento circular é S(1)-S(2) =5.pi/36-sen(50°)/2 =0.4361-0.3830=0.0531 Resposta b) Eu tb fiz assim , mas acho que isto caíu em algum concurso (ñ sei muito bem), e creio que a pessoa ñ teria acesso a seno de 50 graus, logo ñ teria um modo de descobrir o seno deste, geometricamente na figura? Um abraço Felipe -- Início da mensagem original --- De: [EMAIL PROTECTED] Para: [EMAIL PROTECTED] Cc: Data: Fri, 14 May 2004 22:34:06 -0400 Assunto: RE: [obm-l] área Ainda ñ consegui matar aquela segunda mais tõ tentando enquanto a origem, tb acho que foi de alguma obm só ñ sei o ano, se alguém descobrir me avisem. Hoje quando estava voltando para casa um amigo me propôs uma questão e fiquei meio em dúvida, aí vai: Seja S a área de um segmento circular de 50 graus, numa circunferência de raio unitário,pode-se afirmar que: a)0,02S0,04 b)0,04S0,09 c)0,09S0,70 d)0,25S0,30 S360 = 3.14 S50 = 0.44 opcao (c) Essa ñ seria a área do setor circular?,ele quer do segmento circular Um abraço Felipe Santana ___ _ _ Express yourself with the new version of MSN Messenger! Download today - it's FREE! http://messenger.msn.click- url.com/go/onm00200471ave/direct/01/ === = = 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 === = = ___ ___ 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 === == Atenciosamente, Engenharia Elétrica - UNESP Ilha Solteira Osvaldo Mello Sponquiado Usuário de GNU/Linux __ 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 = __ 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 =
Re: [obm-l] provas
-- Início da mensagem original --- De: [EMAIL PROTECTED] Para: [EMAIL PROTECTED] Cc: Data: Fri, 14 May 2004 16:51:28 -0300 Assunto: Re: [obm-l] provas Eu gostaria de te-las. [EMAIL PROTECTED] Grato Daniel gostaria também de tê-las. [EMAIL PROTECTED] Agradeço desde de já. Aristoteles camara - Original Message - From: leandro-epcar [EMAIL PROTECTED] To: obm-l [EMAIL PROTECTED] Sent: Friday, May 14, 2004 12:49 PM Subject: [obm-l] provas estou com quatro provas do colegio naval na mão , os que qrerem elas ,entre em contato __ 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 = = 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 = __ 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 =
[obm-l] Combinatória
oi pessoal , ajude-me nesta questão: De quantas maneiras 7 brinquedos podem ser divididos entre 3 crianças, se a mais nova ganha 3 e cada uma das outras ganha 2?-- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo.
[obm-l] Geometria Analtica
1) Prove analiticamente que o lugar geomtrico dos pontos cuja razo entre as distncias a dois pontos fixos A e B constante, uma circunferncia. 2) Mostre analiticamente que o lugar geometrico cuja soma do quadrado das distncias a dois pontos fixos constante, uma circunferncia. 3) Mostre analiticamente que o luga geometrico cuja diferena entre os quadrados das distncias a dois pontos fixos constante, uma reta. 4) Prove geometricamente cada lugar geometrico do exerccio 1. 5) Provar que d(A,C) d(A,B) + d(B,C). = Instrues 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] Dominos e Fibonacci
Durante a semana, fiquei pensando sobre esse problema e alguns outros, cheguei a algumas conclusões sobre as quais escrevo agora. Suponhamos um tabuleiro 2x1: _ |_| |_| Há uma única possibilidade de disposição do dominó (suposto simétrico). Agora, um tabuleiro 2x2: _ _ |_|_| |_|_| Temos duas possibilidades: dois dominós na horizontal ou dois dominós na vertical. Seja um tabuleiro 2x3: _ _ _ |_|_|_| |_|_|_| Temos três possibilidades: três dominós na vertical, dois à esquerda na horizontal e um na vertical, dois à direita na horizontal e um na vertical. Para um tabuleiro 2x4: _ _ _ _ |_|_|_|_| |_|_|_|_| Há cinco possibilidades: quatro dominós na vertical, dois à esquerda na horizontal e dois na vertical, dois à direita na horizontal e dois na vertical, dois dominós na horizontal no centro e um dominó na vertical em cada extremo, quatro dominós na horizontal. Curiosamente: 2x1 --- 1 possibilidade --- F(2) = 1 2x2 --- 2 possibilidades --- F(3) = 2 2x3 --- 3 possibilidades --- F(4) = 3 2x4 --- 5 possibilidades --- F(5) = 5 2xn --- F(n+1) possibilidades, em que F(n) é o enésimo número de Fibonacci. Quanto ao problema que eu havia proposto (probabilidade e quadradinhos), os tabuleiros são quadrados. Seja um tabuleiro 2x2: _ _ |_|_| |_|_| Temos duas possibilidades na horizontal e outras duas na vertical, i.e., 2*2 = 4 possibilidades. Vamos ao 3x3: _ _ _ |_|_|_| |_|_|_| |_|_|_| Temos 2*3 possibilidades na horizontal (duas possibilidades para cada coluna). Na vertical, por simetria, temos outras 2*3 possibilidades, o que nos dá 2*2*3 = 12 possibilidades. Se tivéssemos um tabuleiro 4x4: _ _ _ _ |_|_|_|_| |_|_|_|_| |_|_|_|_| |_|_|_|_| Teríamos 3*4 possibilidades na horizontal e, por simetria, 3*4 possibilidades na vertical: 2*3*4 = 24 possibilidades. Analogamente, um tabuleiro nxn teria n(n-1) possibilidades na horizontal (para cada coluna, n-1 possibilidades) e, por simetria novamente, n(n-1) na vertical, o que nos traz o resultado que o Cláudio utilizou: 2n(n-1). Na lista também foi proposto um problema sobre sapos na escada pelo Anderson (também conhecido por Dirichlet --- agora com a identidade secreta revelada). Reformulando o problema, em vez de uma escada, imaginemos tocas: x |_|_|_|_|_|_|_|_|_|_|_| O objetivo do sapo é, sem retroceder, partir de x e chegar novamente ao chão. Supondo que haja apenas duas tocas, teremos: - Do chão, o sapo salta e cai na 1a. toca, salta e cai na 2a., salta e vai para o chão; - Do chão, o sapo salta e cai na 1a. toca, salta e vai para o chão; - Do chão, o sapo salta e cai na 2a. toca, salta e vai para o chão. Para duas tocas, temos 3 possibilidades. E se fossem três tocas? - Do chão, o sapo salta e cai na 1a. toca, salta e cai na 2a., salta e cai na 3a., salta e vai para o chão; - Do chão, o sapo salta e cai na 1a. toca, salta e cai na 2a., salta e vai para o chão; - Do chão, o sapo salta e cai na 1a. toca, salta e cai na 3a., salta e vai para o chão; - Do chão, o sapo salta e cai na 2a. toca, salta e cai na 3a., salta e vai para o chão; - Do chão, o sapo salta e cai na 2a. toca, salta e vai para o chão. Para três tocas, temos 5 possibilidades. Mas... e se fossem quatro tocas? Em vez de enumerarmos as possibilidades, observemos que o sapo, no máximo, dará 5 saltos. Se encontrarmos/contarmos todas as partições de 5 em 1 e 2, partições estas em que a ordem é importante, teremos: 5 = 1 + 1 + 1 + 1 + 1 = = 2 + 1 + 1 + 1 = = 1 + 2 + 1 + 1 = = 1 + 1 + 2 + 1 = = 1 + 1 + 1 + 2 = = 2 + 2 + 1 = = 2 + 1 + 2 = = 1 + 2 + 2 Conseguimos oito partições, o que significa que o sapo terá oito possibilidades quando houver quatro tocas. Curiosamente de novo: 1 toca --- 2 possibilidades --- F(3) 2 tocas --- 3 possibilidades --- F(4) 3 tocas --- 5 possibilidades --- F(5) 4 tocas --- 8 possibilidades --- F(6), em que F(n) é o enésimo número de Fibonacci. Assim, quando houver n tocas (ou n degraus, no problema original), o sapo terá F(n+2) maneiras de chegar ao chão (ou ao topo da escada). Abraços, Rafael de A. Sampaio - Original Message - From: Claudio Buffara [EMAIL PROTECTED] To: Lista OBM [EMAIL PROTECTED] Sent: Sunday, May 09, 2004 7:49 PM Subject: [obm-l] Dominos e Fibonacci De quantas maneiras podemos cobrir um tabuleiro 2xn com dominos? Suponha que os dominos sao simetricos (ou seja, ambos os quadrados tem o mesmo numero de bolinhas). = 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] Re:[obm-l] Re:[obm-l] RE: [obm-l] área
From: biper [EMAIL PROTECTED] A área do seg. circ. corresponde à área do setor circular menos a àrea do triangulo isosceles formado. I) Area do setor 360 - pi.1^2 50 - S(1) S(1)=5pi/36 II) Area do tring. O triagulo tem lados 1 1 e angulo entre estes lados de 50°, logo S(2)=1.1.sen(50°)/2 III) Area do seg. circ. Portanto a àrea do segmento circular é S(1)-S(2) =5.pi/36-sen(50°)/2 =0.4361-0.3830=0.0531 Resposta b) Eu tb fiz assim , mas acho que isto caíu em algum concurso (ñ sei muito bem), e creio que a pessoa ñ teria acesso a seno de 50 graus, logo ñ teria um modo de descobrir o seno deste, geometricamente na figura? Um abraço Felipe Puts... e oke da nao ler a questao direito... mas como ja responderam so vou comentar quanto a nao saber o seno de 50. As opcoes todas te dao um intervalo, entao vo nao precisa saber o valor exato da area basta saber que S60 S50 S45 e estes sao angulos ki todo mundo sabe o seno _ Watch LIVE baseball games on your computer with MLB.TV, included with MSN Premium! http://join.msn.click-url.com/go/onm00200439ave/direct/01/ = 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] Combinatória
Não faz muito tempo que essa questão passou pela lista. Veja a primeira das questões: http://www.mail-archive.com/[EMAIL PROTECTED]/msg20517.html E, antes de enviar um problema, não custa dar uma olhada nos arquivos da lista... Um abraço, Rafael - Original Message - From: Pedro Costa To: [EMAIL PROTECTED] Sent: Saturday, May 15, 2004 1:58 PM Subject: [obm-l] Combinatória oi pessoal , ajude-me nesta questão: De quantas maneiras 7 brinquedos podem ser divididos entre 3 crianças, se a mais nova ganha 3 e cada uma das outras ganha 2? = 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] Re:[obm-l] Re:[obm-l] RE: [obm-l] área
Okay, talvez seja interessante interpolar. Fazendo f(x)=sen(x) dai conhecemos f(45º) e f(60°) encontro o polinomio interpolador entre os pontos e calculo a aproximaçao, seria uma alternativa. -- Início da mensagem original --- De: [EMAIL PROTECTED] Para: quot;obm-lquot; [EMAIL PROTECTED] Cc: Data: Sat, 15 May 2004 11:00:14 -0300 Assunto: [obm-l] Re:[obm-l] RE: [obm-l] área A área do seg. circ. corresponde à área do setor circular menos a àrea do triangulo isosceles formado. I) Area do setor 360 - pi.1^2 50 - S(1) S(1)=5pi/36 II) Area do tring. O triagulo tem lados 1 1 e angulo entre estes lados de 50°, logo S(2)=1.1.sen(50°)/2 III) Area do seg. circ. Portanto a àrea do segmento circular é S(1)-S(2) =5.pi/36-sen(50°)/2 =0.4361-0.3830=0.0531 Resposta b) Eu tb fiz assim , mas acho que isto caíu em algum concurso (ñ sei muito bem), e creio que a pessoa ñ teria acesso a seno de 50 graus, logo ñ teria um modo de descobrir o seno deste, geometricamente na figura? Um abraço Felipe -- Início da mensagem original -- - De: [EMAIL PROTECTED] Para: [EMAIL PROTECTED] Cc: Data: Fri, 14 May 2004 22:34:06 -0400 Assunto: RE: [obm-l] área Ainda ñ consegui matar aquela segunda mais tõ tentando enquanto a origem, tb acho que foi de alguma obm só ñ sei o ano, se alguém descobrir me avisem. Hoje quando estava voltando para casa um amigo me propôs uma questão e fiquei meio em dúvida, aí vai: Seja S a área de um segmento circular de 50 graus, numa circunferência de raio unitário,pode-se afirmar que: a)0,02S0,04 b)0,04S0,09 c)0,09S0,70 d)0,25S0,30 S360 = 3.14 S50 = 0.44 opcao (c) Essa ñ seria a área do setor circular?,ele quer do segmento circular Um abraço Felipe Santana ___ _ _ Express yourself with the new version of MSN Messenger! Download today - it's FREE! http://messenger.msn.click- url.com/go/onm00200471ave/direct/01/ === = = 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 === = = ___ ___ 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 === == Atenciosamente, Engenharia Elétrica - UNESP Ilha Solteira Osvaldo Mello Sponquiado Usuário de GNU/Linux ___ _ __ 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 === = = ___ ___ 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 === == Atenciosamente, Engenharia Elétrica - UNESP Ilha Solteira Osvaldo Mello Sponquiado Usuário de GNU/Linux __ 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 =
[obm-l] maio1
1)Juliano escreveu 5 números inteiros positivos, não necessariamente distintos, tais que seu produto seja igual a sua soma. quais podem ser os números que juliano escreveu?
[obm-l] RE: [obm-l] Re:[obm-l] Re:[obm-l] RE: [obm-l] área
é... isto é verdade... mais a exatidão sempre é preferível, mais nem sempre necessaria. outra forma é usar que sen x é aproximadamente a x radianos e usar a formula sen(45+5) From: biper [EMAIL PROTECTED] A área do seg. circ. corresponde à área do setor circular menos a àrea do triangulo isosceles formado. I) Area do setor 360 - pi.1^2 50 - S(1) S(1)=5pi/36 II) Area do tring. O triagulo tem lados 1 1 e angulo entre estes lados de 50°, logo S(2)=1.1.sen(50°)/2 III) Area do seg. circ. Portanto a àrea do segmento circular é S(1)-S(2) =5.pi/36-sen(50°)/2 =0.4361-0.3830=0.0531 Resposta b) Eu tb fiz assim , mas acho que isto caíu em algum concurso (ñ sei muito bem), e creio que a pessoa ñ teria acesso a seno de 50 graus, logo ñ teria um modo de descobrir o seno deste, geometricamente na figura? Um abraço Felipe Puts... e oke da nao ler a questao direito... mas como ja responderam so vou comentar quanto a nao saber o seno de 50. As opcoes todas te dao um intervalo, entao vo nao precisa saber o valor exato da area basta saber que S60 S50 S45 e estes sao angulos ki todo mundo sabe o seno ___ __ Watch LIVE baseball games on your computer with MLB.TV, included with MSN Premium! http://join.msn.click- url.com/go/onm00200439ave/direct/01/ === == 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 === == Atenciosamente, Engenharia Elétrica - UNESP Ilha Solteira Osvaldo Mello Sponquiado Usuário de GNU/Linux __ 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 =
Re: [obm-l] Dominos e Fibonacci
Veja que o que você constatou faz todo o sentido... Para 2x1 temos 1 possibilidade e para 2x2 temos 2 possibilidades... Seja F(k) = # maneiras de dispor peças de dominó num tabuleiro 2 x k. Então F(k+2) = F(k+1) + F(k) pelo seguinte raciocínio, Se na primeira coluna colocamos um dominó na vertical, devemos preencher um tabuleiro 2 x (k+1) com dominós e isso pode ser feito de F(k+1) maneiras, se nas duas primeiras colunas temos 2 dominós horizontais, então o resto do tabuleiro (2 x k) deve ser preenchido com dominós e isso pode ser feito de F(k) maneiras. [ ]'s = 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] Exercícios sobre máximos e mínimos
Se possível, mandem a resolução detalhada. Desde já, obrigado. 40) Uma pirâmide tem base quadrada e quatro faces triangulares com igual inclinação. Se a área total da base e das faces é dada, mostre que o volume é máximo quando a altura é sqrt(2) vezes a aresta da base. 41) Um cilindro é gerado girando-se um retângulo ao redor do eixo x, onde a base do retângulo está apoiada. Seus vértices superiores estão sobre a curva y=x/(x²+1). Qual é o maior volume que tal cilindro pode ter? 43) Um corredor de largura a forma um ângulo reto com um segundo corredor de largura b. Uma barra longa, fina e pesada deve ser empurrada do piso do primeiro corredor para o segundo. Qual o comprimento da maior barra que pode passar a esquina?
Re:[obm-l] maio1
abcde=a+b+c+d+e se tds sao iguais vem a^5 1)Juliano escreveu 5 números inteiros positivos, não necessariamente distintos, tais que seu produto seja igual a sua soma. quais podem ser os números que juliano escreveu? Atenciosamente, Engenharia Elétrica - UNESP Ilha Solteira Osvaldo Mello Sponquiado Usuário de GNU/Linux __ 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 =
Re: [obm-l] maio1
Title: Re: [obm-l] maio1 on 15.05.04 17:24, Eduardo Soares at [EMAIL PROTECTED] wrote: 1)Juliano escreveu 5 números inteiros positivos, não necessariamente distintos, tais que seu produto seja igual a sua soma. quais podem ser os números que juliano escreveu? Achei esse bonitinho. Aqui vai minha tentativa: Os numeros sao (1,1,2,2,2); (1,1,1,3,3); (1,1,1,2,5). Sejam os numeros: a = b = c = d = e. Investiguemos inicialmente o caso: a = b = c = d = 1. e = 4 + e == 0 = 4 == nao existe solucao nesse caso Seja F:N^5 - N dada por: F(a,b,c,d,e) = abcde - a - b - c - d - e F(a,b,c,d,e+1) - F(a,b,c,d,e) = abcd - 1 0 a menos que a = b = c = d = 1. No entanto jah vimos que esse caso nao nos interessa. Isso significa que o produto cresce mais rapido do que a soma. Ou seja, se existe uma solucao (a,b,c,d,e), entao, se aumentarmos qualquer coordenada, obteremos uma nova quintupla ordenada onde o produto supera a soma. Observe agora que 1*1*2*2*2 = 1+1+2+2+2 = 8. Assim, (1,1,2,2,2) eh uma solucao e, alem disso, se aumentarmos qualquer coordenada, obteremos uma quintupla que nao eh solucao. Isso significa que, em qualquer solucao, devemos ter a = b = 1. Alem disso, se c 1, entao a unica solucao eh (1,1,2,2,2). Logo, falta apenas investigar o caso em que a= b = c = 1, d 1. Nesse caso, teremos que: de = 3 + d + e == e | d + 3 == d = e = d + 3 e = d == d^2 = 3 + 2d == d^2 - 2d - 3 = 0 == d = e = 3 e = d+1 == d(d+1) = 4 + 2d == d^2 - d - 4 = 0 == nao tem solucao inteira e = d+2 == d(d+2) = 5 + 2d == d^2 - 5 = 0 == nao tem solucao inteira e = d+3 == d(d+3) = 6 + 2d == d^2 + d - 6 = 0 == d = 2, e = 5 Logo, achamos as solucoes (1,1,1,3,3) e (1,1,1,2,5) []s, Claudio.
Re: [obm-l] Re: [obm-l] Fw:_sub-seq üência_de_{1,...,204}(*um problema parecido na Ibero*)
on 14.05.04 18:28, Domingos Jr. at [EMAIL PROTECTED] wrote:
ok, matei o problema!!!
o valor crítico é 65!!!
aqui eu demonstro que o limitante superior é 65, supondo que vcs
demonstraram corretamente que o limite inferior é 65, acabou!
Seja S = {s_1, ..., s_n} contido em {1,2,3, ..., 2004}
com s_1 s_2 ... s_n
defina d_i = s_{i+1} - s_i, i = 1..n-1
se para algum i, d_i = d_{i+j} com j = 2
s_{i+1} - s_i = s_{i+j+1} - s_{i+j}
= s_{i+j} + s_{i+1} = s_{i+j+1} + s_i
i i + 1 i+j i+j+1 e portanto temos 4 elementos em S do jeito que
queremos.
supondo que não tenhamos isso...
seja 1 = i i + j k k + m = n
veja que
s_i + s_{k+m} = s_{i+j} + s_k =
s_{k+m} - s_k = s_{i+j} - s_i =
(s_{k+m} - s_{k+m-1}) + (s_{k+m-1} - s_{k+m-2}) ... + (s_{k+1} - s_k) =
(s_{i+j} - s_{i+j-1}) + ... + (s_{i+1} - s_i) =
d_{k+m-1} + d_{k+m-2} + ... + d_k = d_{i+j-1} + ... + d_i
portanto provamos que duas somas consecutivas de elementos de {d_i},
isoladas, não podem ser iguais.
fixe um inteiro i 1 e suponha a i, b = i com
(1) d_a + ... + d_{i-1} = d_i + ... + d_b de forma que b - a é máximo
suponha que tenhamos também a' i, b' = i com
d_{a'} + ... + d_{i-1} = d_i + ... + d_{b'}
não podemos ter b' b, pois o lado direito da soma seria maior que (1) e o
lado esquerdo só poderia aumentar de tamanho contrariando a hipótese de b -
a ser máximo.
se i = b' b, a a' i e aí devemos ter
d_a + ... + d_{a' - 1} = d_{b' + 1} + ... + d_b, o que é absurdo, pois essas
são duas somas consecutivas isoladas.
então mostramos que para i = 2,..., n há no máximo 2 sub-seqüências
consecutivas de mesma soma...
temos um total de Binomial(n-1, 2) subseqüências possíveis (basta escolher
um índice para o começo e outro para o final) e no máximo n-1 são contadas
duas vezes, ou seja, temos pelo menos Binomial(n-1, 2) + 1 - n subseqüências
consecutivas com somas DISTINTAS, note que tais somas representam distâncias
entre elementos de S e, como no nosso caso, S contido em {1,..., 2004}, há
2003 possíveis diferenças logo,
Binomial(n-1, 2) + 1 - n = 2003
(n-1)(n-2)/2 + (1-n) = 2003
(n-1)(n-4) = 4006
n = 65
[ ]'s
Oi, Domingos:
Li e reli o seu argumento e nao achei nenhum furo.
Se estiver mesmo OK (colegas da lista, por favor deem sua opiniao tambem),
ele terah sido um grande passo pra solucao.
Infelizmente, como o Auggy apontou, o limitante inferior de 65 estava
errado.
Logo, estamos com 38 = Ncritico = 66 (os dois limitantes sao seus).
Mas a melhor noticia eh que esse estah sendo um problema dificil no qual
varios participantes da lista estao pensando. Acho que isso eh um exemplo de
como essa lista pode ser interessante e valiosa.
[]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
=
