Re: [obm-l] IME 96
Essa é mais ou menos a idéia do queé conhecido em computação como "Programação Dinâmica" Muito interessante mesmo. Até mais Vinicius Fortuna - Original Message - From: Eduardo Casagrande Stabel To: [EMAIL PROTECTED] Sent: Sunday, November 24, 2002 9:59 PM Subject: Re: [obm-l] IME 96 Olá, essa questão também caiu na Olimpíada Gaúcha de Matemática. Eu pensei na mesma solução da banca. Mas uma das alunas que fez a prova deu uma solução mais simples, e que eu achei até mais apropriada ao tamanho do tabuleiro. Ela começou escrevendo um 1 no canto superior esquerdo. Para cada quadrado seguinte ela preenchia ele com a soma dos números escritos nos quadrados da esq. da dir. e da diagonal superior esq. Assim ela foi preenchendo o tabuleiro e o número final obtido no inferior direito foi a quantidade de maneiras de se chegar até ele. Interessante, né? Duda.
Re: [obm-l] violencia e axioma da escolha
Não sei se entendi direito, mas, ao meu ver, não teríamos conjuntos dois a dois disjuntos e tal propriedade é necessária para aplicar o axioma da escolha (ou não?). De qualquer forma, não poderíamos mapear os bandidos nos números inteiros? Assim teríamos uma função de escolha que pegaria em C o bandido mapeado no menor inteiro tal que satisfaça aquelas condições para entrar em R. Se temos uma função de escolha então podemos escolhê-los independentemente do axioma da escolha. Agradeço esclarecimentos Vinicius Fortuna - Original Message - From: Rogerio Fajardo [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Monday, September 09, 2002 12:08 PM Subject: Re: [obm-l] violencia Olá, Vinicius Cada vez que voce retira um elemento de C e coloca em R, na verdade voce mudou o conjunto C. Ou seja, cada escolha que voce fez, no processo indutivo, foi sobre um conjunto diferente. É semelhante a demonstração de que todo conjunto infinto possui um subconjunto enumerável, em que, dado um conjunto V, construímos indutivamente um conjunto S colocando nele, a cada passo, um elemento de V que não está em S, usando o Axioma da Escolha From: Vinicius José Fortuna [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] violencia Date: Sun, 8 Sep 2002 18:41:45 -0300 Oi Rogério Acho que não saquei. Em que momento foi utilizado o axioma da escolha? Eu nem tinha infinitos conjuntos! Apenas conjuntos infinitos. Até mais Vinicius - Original Message - From: Rogerio Fajardo [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Sunday, September 08, 2002 2:17 PM Subject: Re: [obm-l] violencia É bom notar que essa solução usa o axioma da escolha (de infinitos conjuntos não-vazios, escolhemos um elemento de cada). É essencial o axioma da escolha para resolvê-lo? From: Vinicius José Fortuna [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] violencia Date: Sat, 7 Sep 2002 23:44:58 -0300 - Original Message - From: Fernanda Medeiros [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, September 07, 2002 8:45 PM Subject: [obm-l] violencia Olá, alguém pode dar uma ajuda nestas questões? 1.a)uma gang tem infinitos bandidos e cada um dos meliantes tem um único inimigo no interior da gang,que ele quer matar.Prove q é possivel reunir uma quantidade infinita de bandidos desta gang, semq haja o risco de q um bandido mate outro durante a reunião. Pense no seguinte algoritmo: Temos o conjunto C de candidatos à reunião que inicialmente contém todos os infinitos bandidos da gangue. Temos o conjunto R de bandidos selecionados para a reunião que inicialmente está vazio. A cada passo do algoritmo procuramos em C alguém que não que matar ninguém de R e ninguém em R quer matá-lo. Seja M o subconjunto de C de bandidos que pelo menos um de R quer matar. Como cada bandido de R só quer matar um, |M|=|R| Então, como R é finito, M será finito e V=C-M será infinito, pois C é infinito. V será o subconjunto de C dos bandidos que ninguém de R quer matar. Em V procuramos um bandido que não quer matar ninguém de R, retiramos ele de C, o inserimos em R e repete-se o processo. Se sempre for possível encontrar tal bandido, o processo se repetirá indefinidamente e com R sempre crescendo. Assim teremos infnitos bandidos na reunião sem derramamento de sangue. Se em algum momento não for possível encontrar um bandido em V, é porque todos os bandidos de V querem matar alguém de R. Ou seja, ninguém de V quer matar outro de V. Pegamos, então, V como o conjunto de bandidos para a reunião. Como V é infinito, teremos infinitos participantes na reunião. b)Se cada bandido tiver um nº finito mas indefinido de inimigos(um bandido pode ter 2 inimigos, outro somente 1, um terceiro pode ter 20 e assim por diante).Será sempre possivel promover uma reunião com infinitos bandidos sem risco de derramamento de sangue? Não é possível. Existe um contra-exemplo: Ordene os bandidos formando uma sequência. Imagine que cada bandido quer matar todos que vêm antes dele na sequência. Nunca poderemos ter dois bandidos 'a' e 'b' na reunião, pois ou a vem antes de b, ou b vem antes de, assim haverá um que vai querer matar o outro. Então só poderemos ter um bandido na reunião. Até mais Vinicius Fortuna IC-Unicamp = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] violencia
Title: RE: [obm-l] violencia Existe uma passagem que, ao meu ver, está falsa. Observe abaixo. - Original Message - From: Artur Costa Steiner To: [EMAIL PROTECTED] Sent: Sunday, September 08, 2002 11:24 AM Subject: RE: [obm-l] violencia Bom, com relação à primeira questão. Comecemos pela segunda parte e suponhamos, conforme vc disse, que cada bandido tenha um número finito de inimigos. Vou supor que, embora variando com o bandido, este número é conhecido para cada bandido. Escolha um bandido. Isto é possível pois há infinitos (Meu Deus!!) Dado que este bandido tem um número finito de inimigos e existem infinitos bandidos, podemos escolher um bandido que não seja inimigo dele. Logo, a base de nosso processo indutivo está formada. Suponhamos agora que, para algum natural n, tenhamos escolhido n bandidos tais que ninguém seja inimigo de ninguém. Suponhamos. Ora, cada um destes n bandidos tem um número apenas finito de inimigos. Logo, o número total de bandidos que são inimigos de um destes n bandidos escolhidos é finito - pois é a soma de n parcelas finitas.. Mas, temos infinitos bandidos, de modo que podemos escolher um que não seja inimigo de nenhum dos n que já escolhemos (e, é claro, que não seja um membro deste conjunto de n que escolhemos). Com isto, obtemos n +1 bandidos distintos tais que, neste conjunto, ninguém vai matar ninguém. Não basta que ele não seja inimigo de nenhum que já foi escolhido, mas tbnenhum dosque já foram escolhidospode ser inimigodele. Pode haver o caso em que todos os infinitos bandidos restantes querem matar alguém do grupo que já foi escolhido. Neste caso o grupo da reunião não poderia ser aumentado. Observe a mensagem que mandei anteriormente. Até mais Vinicius Fortuna A "ponte" de nosso processo indutivo está portanto formada, e mostra que nosso processo de escolha pode prosseguir indefinidamente. OK? Podemos dizer que geramos um seqüência B_n de bandidos tal que, dados quaisquer naturais m e n, com mn, então B_n não quer matar B_m. Estou assumindo, implicitamente, que ninguém quer cometer suicídio. A primeira parte de sua 1a questão é um caso particular da segunda, obtida quando cada bandido tem apenas um inimigo. Espero ter ajudado Artur
Re: [obm-l] violencia
Oi Rogério Acho que não saquei. Em que momento foi utilizado o axioma da escolha? Eu nem tinha infinitos conjuntos! Apenas conjuntos infinitos. Até mais Vinicius - Original Message - From: Rogerio Fajardo [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Sunday, September 08, 2002 2:17 PM Subject: Re: [obm-l] violencia É bom notar que essa solução usa o axioma da escolha (de infinitos conjuntos não-vazios, escolhemos um elemento de cada). É essencial o axioma da escolha para resolvê-lo? From: Vinicius José Fortuna [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] violencia Date: Sat, 7 Sep 2002 23:44:58 -0300 - Original Message - From: Fernanda Medeiros [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, September 07, 2002 8:45 PM Subject: [obm-l] violencia Olá, alguém pode dar uma ajuda nestas questões? 1.a)uma gang tem infinitos bandidos e cada um dos meliantes tem um único inimigo no interior da gang,que ele quer matar.Prove q é possivel reunir uma quantidade infinita de bandidos desta gang, semq haja o risco de q um bandido mate outro durante a reunião. Pense no seguinte algoritmo: Temos o conjunto C de candidatos à reunião que inicialmente contém todos os infinitos bandidos da gangue. Temos o conjunto R de bandidos selecionados para a reunião que inicialmente está vazio. A cada passo do algoritmo procuramos em C alguém que não que matar ninguém de R e ninguém em R quer matá-lo. Seja M o subconjunto de C de bandidos que pelo menos um de R quer matar. Como cada bandido de R só quer matar um, |M|=|R| Então, como R é finito, M será finito e V=C-M será infinito, pois C é infinito. V será o subconjunto de C dos bandidos que ninguém de R quer matar. Em V procuramos um bandido que não quer matar ninguém de R, retiramos ele de C, o inserimos em R e repete-se o processo. Se sempre for possível encontrar tal bandido, o processo se repetirá indefinidamente e com R sempre crescendo. Assim teremos infnitos bandidos na reunião sem derramamento de sangue. Se em algum momento não for possível encontrar um bandido em V, é porque todos os bandidos de V querem matar alguém de R. Ou seja, ninguém de V quer matar outro de V. Pegamos, então, V como o conjunto de bandidos para a reunião. Como V é infinito, teremos infinitos participantes na reunião. b)Se cada bandido tiver um nº finito mas indefinido de inimigos(um bandido pode ter 2 inimigos, outro somente 1, um terceiro pode ter 20 e assim por diante).Será sempre possivel promover uma reunião com infinitos bandidos sem risco de derramamento de sangue? Não é possível. Existe um contra-exemplo: Ordene os bandidos formando uma sequência. Imagine que cada bandido quer matar todos que vêm antes dele na sequência. Nunca poderemos ter dois bandidos 'a' e 'b' na reunião, pois ou a vem antes de b, ou b vem antes de, assim haverá um que vai querer matar o outro. Então só poderemos ter um bandido na reunião. Até mais Vinicius Fortuna IC-Unicamp = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] violencia
- Original Message - From: Fernanda Medeiros [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, September 07, 2002 8:45 PM Subject: [obm-l] violencia Olá, alguém pode dar uma ajuda nestas questões? 1.a)uma gang tem infinitos bandidos e cada um dos meliantes tem um único inimigo no interior da gang,que ele quer matar.Prove q é possivel reunir uma quantidade infinita de bandidos desta gang, semq haja o risco de q um bandido mate outro durante a reunião. Pense no seguinte algoritmo: Temos o conjunto C de candidatos à reunião que inicialmente contém todos os infinitos bandidos da gangue. Temos o conjunto R de bandidos selecionados para a reunião que inicialmente está vazio. A cada passo do algoritmo procuramos em C alguém que não que matar ninguém de R e ninguém em R quer matá-lo. Seja M o subconjunto de C de bandidos que pelo menos um de R quer matar. Como cada bandido de R só quer matar um, |M|=|R| Então, como R é finito, M será finito e V=C-M será infinito, pois C é infinito. V será o subconjunto de C dos bandidos que ninguém de R quer matar. Em V procuramos um bandido que não quer matar ninguém de R, retiramos ele de C, o inserimos em R e repete-se o processo. Se sempre for possível encontrar tal bandido, o processo se repetirá indefinidamente e com R sempre crescendo. Assim teremos infnitos bandidos na reunião sem derramamento de sangue. Se em algum momento não for possível encontrar um bandido em V, é porque todos os bandidos de V querem matar alguém de R. Ou seja, ninguém de V quer matar outro de V. Pegamos, então, V como o conjunto de bandidos para a reunião. Como V é infinito, teremos infinitos participantes na reunião. b)Se cada bandido tiver um nº finito mas indefinido de inimigos(um bandido pode ter 2 inimigos, outro somente 1, um terceiro pode ter 20 e assim por diante).Será sempre possivel promover uma reunião com infinitos bandidos sem risco de derramamento de sangue? Não é possível. Existe um contra-exemplo: Ordene os bandidos formando uma sequência. Imagine que cada bandido quer matar todos que vêm antes dele na sequência. Nunca poderemos ter dois bandidos 'a' e 'b' na reunião, pois ou a vem antes de b, ou b vem antes de, assim haverá um que vai querer matar o outro. Então só poderemos ter um bandido na reunião. Até mais Vinicius Fortuna IC-Unicamp = 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 O administrador desta lista é [EMAIL PROTECTED] =
[obm-l] Re: [obm-l] Números Complexos
- Original Message - From: Tonik [EMAIL PROTECTED] Subject: Re: [obm-l] Números Complexos 1) Obtenha o argumento de sen 40º + i cos 40º obviamente, 40º Não seria 50 graus? Ângulos em graus: sen 40 + i cos 40 = cos(90-40) + i sen(90-40) = cos 50 + i sen 50 Logo, 50 graus. Até mais Vinicius Fortuna = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] (nenhum assunto)
- Original Message - From: [EMAIL PROTECTED] Subject: [obm-l] (nenhum assunto) 1)Se a e b são números primos entre si, prove que mdc(a+b,a^2+ab+b^2)=1 mdc(a+b,a^2+ab+b^2) = mdc(a+b, (a+b)^2 -ab) Existe a propriedade que mdc(x, y) = mdc(x, y-nx) fazendo x=a+b, y=(a+b)^2 - ab, n = a temos: mdc(a+b, (a+b)^2 -ab) = mdc(a+b, b^2) = M M | b^2 = M | b b = kM, k inteiro M | (a+b) = (a+b)/M = p, p inteiro a/M + k = p a/M = p-k = M | a M | a e M | b e mdc(a, b)=1 = M=1 mdc(a+b,a^2+ab+b^2) = M =1 2) Prove que sen(20graus) é irracional. Os ângulos estão em graus: sen(60) = sen(40+20) = sen(40) cos(20) + sen(20) cos(40) sen(40) = sen(2*20) = 2*sen(20) cos(20) cos(40) = cos(2*20) = cos(20)^2 - sen(20)^2 = 1 - 2 sen(20)^2 sen(60) = 2 sen(20) cos(20)^2 + sen(20) - 2 sen(20)^3 sen(60) = 2 sen(20) - 2 sen(20)^3 + sen(20) - 2 sen(20)^3 sen(60) = 3 sen(20) - 4 sen(20)^3 Assuma que sen(20) é racional. Soma, subtração, multiplicação e divisão entre racionais dá um racional. Sendo assim sen(60) seria racional, o que é um absurdo, já que sen(60) = sqrt(3)/2 Então sen(20) é irracional. = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] olimpiada virtual
Não sei se é uma boa fazer apenas um grupo para cada estado, posto que a distribuição dos competidores pelos estados não é uniforme. De repente seria legal juntar pessoas de estados diferentes, (por sorteio, talvez) e ver no que dá. Os membros do grupo poderiam discutir os problemas por e-mail. O interessantes é que, normalmente, pessoas de lugares diferentes têm pontos de vista diferentes e pensam de outra forma. Seria uma experiência mais produtiva. Um outra questão: os universitários estariam dentro? Espero que sim :-) Até mais Vinicius Fortuna IC-Unicamp - Original Message - From: Marcelo Souza [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Tuesday, August 27, 2002 12:09 AM Subject: Re: [obm-l] olimpiada virtual Gostei muito dessa sugestao. Achei a mais organizada, porem, naum eh uma coisa soh entre nós. Teríamos que ver qual professor teria paciencia de corrigir, estabelecer criterios de correcao. Naum eh bem simples assim. Talvez fosse bom fazer grupos (se houvessem grupos) de estado em estadotipo, um pro Rio, outro pra sao paulo, etc... = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] Re:
Ops, quis dizer menor. Não existe maior pois: 7/10 (7a + 11b)/(10a + 15b) 11/15 , a, b0 p=7a + 11b q =10a + 15b Podemos aumentar a e b o quanto quisermos para obter q arbitrariamente grande. A desigualdade acima me deu uma idéia para encontrar um limite inferior para q. q = 10a + 15b. Se a e b fossem inteiros livres, teríamos que o menor valor inteiro positivo que q poderia assumir é mdc(10, 15)=5 então q=5 Mas q=5dá a=-1 e b=1, que viola a, b0 Como essa solução é única para q=5, temos que q5 Assim precisaríamos apenas testar q=6 e q=7 Para chegar nas conclusões acima me baseei em teoremas sobre mdc que não sei se têm nomes. Tirei do livro "Introduction to Algorithms" de Cormen, Leiserson e Rivest. Até mais Vinicius Fortuna - Original Message - From: Augusto César Morgado To: [EMAIL PROTECTED] Sent: Tuesday, August 27, 2002 11:33 PM Subject: Re: [obm-l] Re: Maior?MorgadoVinicius José Fortuna wrote: 020301c24e37$9d078a00$0401010a@xt type="cite">Considerando que se procura o maior valor de q.Temos:7/10 (7+11)/(10+15) = 18/25 11/157/10 (7+18)/(10+25) = 25/35 = 5/7 18/15 11/15Por enquanto temos q=7 em 5/7. Precisamos verificar se é o melhor possível.Para isso testamos todos os q, 1=q77/10 p/q 11/15q*7/10 p q*11/15p/ q=17/10 p 11/15- não existe pp/ q=214/10 p 22/154/10 p-1 7/15- não existe pp/ q=321/10 p 33/151/10 p-2 3/15- não existe pp/ q=428/10 p 44/158/10 p-2 14/15- não existe pp/ q=535/10 p 55/155/10 p-3 10/15- não existe pp/ q=642/10 p 66/152/10 p-4 6/15- não existe pSó para confirmar:p/ q=749/10 p 77/154+ 9/10 p 5 + 2/15como p é inteiro:5 = p =5- p=5Até maisVinicius FortunaIC- Unicamp- Original Message -From: "Bruno F. C. Leite" [EMAIL PROTECTED]To: [EMAIL PROTECTED]Sent: Tuesday, August 27, 2002 3:54 AMSubject: [obm-l] Re: At 18:37 26/08/02 -0300, you wrote: Será que alguém poderia me ajudar neste problema:Se p e q são inteiros positivos tais que 7/10 p/q 11/15 ,qual o maiorvalor que q pode assumir?Obrigado.Acho que se trocarmos "maior" por "menor", o enunciado fica maisinteressante. Aí, saber frações de Farey (ou dar um bom chute) pode serútil (mas não imprescindível)Bruno Leitehttp://www.ime.usp.br/~brleite=Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.htmlO administrador desta lista é [EMAIL PROTECTED]=
Re: [obm-l] Re:
Na verdade q não é necessariamente da forma 10a+15b. Isso serviu só para mostrar que não existe o "maior" q possível. Assim aquele limite inferior não vale para qquer q. Snif, eu tinha achado que a idéia era legal.. :-( Foi mal. Acho que estou precisando dormir um pouco. |-O..zzzZZZ Até mais Vinicius Fortuna - Original Message - From: Vinicius José Fortuna To: [EMAIL PROTECTED] Sent: Wednesday, August 28, 2002 12:27 AM Subject: Re: [obm-l] Re: Ops, quis dizer menor. Não existe maior pois: 7/10 (7a + 11b)/(10a + 15b) 11/15 , a, b0 p=7a + 11b q =10a + 15b Podemos aumentar a e b o quanto quisermos para obter q arbitrariamente grande. A desigualdade acima me deu uma idéia para encontrar um limite inferior para q. q = 10a + 15b. Se a e b fossem inteiros livres, teríamos que o menor valor inteiro positivo que q poderia assumir é mdc(10, 15)=5 então q=5 Mas q=5dá a=-1 e b=1, que viola a, b0 Como essa solução é única para q=5, temos que q5 Assim precisaríamos apenas testar q=6 e q=7 Para chegar nas conclusões acima me baseei em teoremas sobre mdc que não sei se têm nomes. Tirei do livro "Introduction to Algorithms" de Cormen, Leiserson e Rivest. Até mais Vinicius Fortuna - Original Message - From: Augusto César Morgado To: [EMAIL PROTECTED] Sent: Tuesday, August 27, 2002 11:33 PM Subject: Re: [obm-l] Re: Maior?MorgadoVinicius José Fortuna wrote: 020301c24e37$9d078a00$0401010a@xt type="cite">Considerando que se procura o maior valor de q.Temos:7/10 (7+11)/(10+15) = 18/25 11/157/10 (7+18)/(10+25) = 25/35 = 5/7 18/15 11/15Por enquanto temos q=7 em 5/7. Precisamos verificar se é o melhor possível.Para isso testamos todos os q, 1=q77/10 p/q 11/15q*7/10 p q*11/15p/ q=17/10 p 11/15- não existe pp/ q=214/10 p 22/154/10 p-1 7/15- não existe pp/ q=321/10 p 33/151/10 p-2 3/15- não existe pp/ q=428/10 p 44/158/10 p-2 14/15- não existe pp/ q=535/10 p 55/155/10 p-3 10/15- não existe pp/ q=642/10 p 66/152/10 p-4 6/15- não existe pSó para confirmar:p/ q=749/10 p 77/154+ 9/10 p 5 + 2/15como p é inteiro:5 = p =5- p=5Até maisVinicius FortunaIC- Unicamp- Original Message -From: "Bruno F. C. Leite" [EMAIL PROTECTED]To: [EMAIL PROTECTED]Sent: Tuesday, August 27, 2002 3:54 AMSubject: [obm-l] Re: At 18:37 26/08/02 -0300, you wrote: Será que alguém poderia me ajudar neste problema:Se p e q são inteiros positivos tais que 7/10 p/q 11/15 ,qual o maiorvalor que q pode assumir?Obrigado.Acho que se trocarmos "maior" por "menor", o enunciado fica maisinteressante. Aí, saber frações de Farey (ou dar um bom chute) pode serútil (mas não imprescindível)Bruno Leitehttp://www.ime.usp.br/~brleite=Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.htmlO administrador desta lista é [EMAIL PROTECTED]=
[obm-l] Re: [obm-l] RES: [obm-l] Numeros primos - solução
Repare que no paper está escrito Õ((log n)^12), com til no O. Essa notação tem um significado diferente. Para ser mais preciso, o algoritmo dos indianos leva, no pior caso, tempo O((log n)^12* f(log log n)), onde f é um polinômio. Para maiores informações sobre o paper, pode-se acessar o site: http://www.utm.edu/research/primes/prove/prove4_3.html Nessa página há um FAQ sobre o paper, seguindo o link Primes in P little faq, que leva ao endereço: http://crypto.cs.mcgill.ca/%7Estiglic/PRIMES_P_FAQ.html O conteúdo dessa página aborda vários pontos interessantes, inclusive o que são as classes de problemas P , NP e algumas outras. Pra quem é curioso vale a pena dar uma olhada. Até mais Vinicius Fortuna. IC-Unicamp - Original Message - From: Rodrigo Malta Schmidt [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Sunday, August 25, 2002 6:17 PM Subject: Re: [obm-l] RES: [obm-l] Numeros primos - solução Ola, A classe de todas as linguagens polinomialmente decidíveis é denotada por P [P do inglês polinomial] e a classe de todas as linguagens que não pertecem a P é denotada por NP [NP do inglês no-polinomial]. NP vem do ingles nondeterministic polynomial time. Problemas (ou linguagens, como voce definiu) em NP nao sao necessariamente nao-polinomiais. Se fossem, teriamos resposta para o problema P=NP. NP representa a classe de problemas para os quais se consegue um algoritmo nao-deterministico que rode em tempo polinomial (equivalente a se conseguir verificar uma saida deterministicamente em tempo polinomial). Todo problema em P necessariamente esta em NP, mas o inverso ainda eh um problema em aberto. De acordo com o documento Primes in P, os autores apresentam um algoritmo que decide se um dado número n é primo ou composto [dei uma lida rápida] com uma complexidade computacional O([log(n)]^6), podendo futuramente chegar a O([log(n)]^3), desde que se prove a conjectura de Bhattacharjee-Pandey. Talvez minha olhada tenha sido mais rapida que a sua, mas eu havia lido o seguinte: We give a deterministic, O((log n)^12) time algorithm for testing if a number is prime. Heuristically, our algorithm does much better: under a widely believed conjecture on the density of Sophie Germain primes (primes p such that 2p+1 is also prime), the algorithm takes only O((log n)^6) steps. Mas realmente, no final do artigo, seguindo outras conjecturas os autores comentam a possibilidade de uma implementacao O((log n)^3). No entanto, enquanto a Conjectura 5 do artigo (Sophie Germain) ainda nao for provada, o algoritmo deles continua tendo complexidade deterministica O((log n)^12), o que, para numeros com 1000 bits por exemplo, nao eh muito viavel na pratica. Minhas referencias sao dos livros: Introduction to Algorithms. Thomas Cormen et al. Introduction to Algorithms - A creative approach. Udi Manber. e do artigo: PRIMES is in P. Agrawal, Kayal e Saxena. Abracos, Rodrigo = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] x inicial
Vc pode tentar esboçar o gráfico da função para ter idéia de alguns valores que podem estar próximos à raiz. Aì vc pega um desses valores como valor inicial para o Método de Newton. Vinicus - Original Message - From: Andre Wulff Hirano [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Wednesday, August 21, 2002 11:38 AM Subject: [obm-l] x inicial No assunto de zeros de funçao , alguem sabe como se estima o valor inicial x0, para aplicar na formula do método de newton? Porque muitos problemas dão apenas a funçao inicial, mas ainda nao entendi como é o critério para saber o valor inicial de x , para começar a fazer as iteraçoes e que os resultados tenham rápida convergencia à raiz da funçao. Se alguem souber explicar , agradeço.. = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] Complexidades P e NP
A seguinte proposição é verdadeira: Todo problema pertencente à classe de complexidade P pertence à classe de complexidade NP. A classe P significa que a solução pode ser verificada em tempo polinomial. A classe NP significa que a solução pode ser verificada não-deterministicamente em tempo polinomial. A proposição de que P está contido em NP vem justamente do fato de que tudo que é determinístico pode ser considerado como não-determinístico. A recíproca da proposição é um problema em aberto. Existe um subconjunto dos NP que são os NP-completos. Todo problema NP se reduz polinomialmente a um problema NP-completo. Isso quer dizer que sempre é possível transformar um problema NP em tempo polinomial em um caso particular de um NP-completo. Dessa forma, se um problema NP-completo puder ser resolvido em tempo polinomial, então, todos os NP também poderão e então teremos P=NP. Acredita-se que P é diferente de NP. Eu preferiria que fossem iguais, as coisas seriam bem mais fáceis. :-) Maiores informação pode-se encontrar em qualquer livro de complexidade de algoritmos Até mais Vinicius Fortuna Ciência da Computação - Unicamp - Original Message - From: Edilon Ribeiro da Silva [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Wednesday, August 14, 2002 8:34 PM Subject: [obm-l] Complexidades P e NP Gostaria de saber se existe algum problema que pertença simultaneamente à classe de complexidade P e à classe de compleidade NP. Edilon Ribeiro. = 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 O administrador desta lista é [EMAIL PROTECTED] =
[obm-l] Re: [obm-l] Re: [obm-l] Tradução de Problema
Podemos resolver esse problema usando Teoria dos Grafos.
Criamos um conjunto X de véritices que representam os números e um conjunto
Y de vértices que representam as cartas.
|X| = |Y| = 100.
Para cada vértice x em X, adicionamos uma aresta (x,y) para cada uma das
duas cartas y em que o número x aparece.
Dessa forma criamos um grafo bipartido, ou bigrafo-X,Y. Um bigrafo-X,Y
significa que não há arestas entre elementos do conjunto X ou entre
elementos do conjunto Y.
Assim queremos um casamento total entre os números em X com as cartas em Y.
Um número x casado com uma carta y significa que a carta y estará com o
número x voltado para cima.
Pelo Teorema de Hall, um bigrafo G tem um casamento que satura X se, e
somente se, |N(S)| = |S| para todo subconjunto S de X
Um casamento que satura X é que casa todos seus elementos. É o que
procuramos.
N(S) é a vizinhança dos vértices em S.
Sendo S um subconjunto de X, considere o subgrafo induzido por S união N(S).
O número de arestas E será 2.|S|, pois cada número em S se liga a duas
cartas em N(S)
Mas pelo Primeiro Teorema da Teoria dos Grafos temos
2.E = Soma{v em S U N(S)} d(v)
Onde d(v) é o número de arestas incidentes a v
Então, como S e N(S) são disjuntos:
4.|S| = [Soma{v em S} d(v)] + [Soma{v em N(S)}d(v)]
Como d(v) = 2 para todo v em S temos
4.|S| = 2.|S| + Soma{v em N(S)}d(v)
Soma{v em N(S)}d(v) = 2.|S|
Mas d(v) = 2 para todo v em N(S), pois cada carta se liga ao no máximo dois
números, então
Soma{v em N(S)} 2 = Soma{v em N(S)}d(v) = 2|S|
2.|N(S)| = 2.|S|
|N(S)| = |S|
Assim conseguimos a condição necessário no Teorema de Hall para provar que
existe um casamento que cubra todos os números em X.
Isso vale para qquer quantidade de números e dois baralhos, em particular
para 100 números, o que resolve o problema proposto.
Até mais
Vinicius Fortuna
- Original Message -
From: Paulo Santa Rita [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Sent: Wednesday, August 14, 2002 8:00 PM
Subject: [obm-l] Re: [obm-l] Tradução de Problema
Ola Duda e demais colegas
desta lista ... OBM-L
O que precisa ser mostrado é exatamente o que pede o enunciado do problema
:
as cem cartas sobre a mesa com os numeros de 1 a 100 visiveis, sem faltar
nenhum deles ...
Em que consiste o problema ?
Nao e evidente que - INDEPENDENTE DA MANEIRA COMO OS NUMEROS FORAM
GRAFADOS
NOS DOIS BARALHOS - seja possivel exibir os 100 numeros, sem que haja
omissao de algum numero. A parte matematica ( algoritmica )da questao
consiste precisamente em mostrar que uma tal exibicao sempre é possivel.
Uma parafrase do problema pode ser : Mostre como isabel pode escolher cada
carta, determinando qual numero ficara por cima e qual ficara por baixo,
de
forma que no final da centesima escolha as faces visiveis exponham os 100
numeros naturais.
Uma sintaxe adequada pode ser :
Sejam A e B os baralhos. Ao escolher uma carta de um dos baralhos (
digamos,
do baralho A ) teremos um par (V,I) em que V e o numero que ficara pra
cima
( visicel ) e I o numero que ficara pra baixo ( invisivel ).O Mesmo vale
para o baralho B.
O inicio de um algoritmo pode ser :
1) Escolha a carta do baralho A onde esta o numero 1. Seja X o numero que
acompanha 1 no baralho A. Colocamos a carta na forma (1,X).
2) Procure a carta do baralho B que tem o numero X. Seja Y o numero que
acompanha o numero X no baralho B. Colocamos esta carta na forma (X,Y)
3) Y=1 ?
Se nao, procure no baralho A ...
E assim sucessivamente. Voce deve mostrar que o algoritmo descrito
permite -
INDEPENDENTE DA MANEIRA COMO OS NUMEROS FORAM GRAFADOS NOS DOIS BARALHOS -
exibir as 100 cartas com os 100 numeros visiveis, sem que nenhum seja
omitido.
Eu nao parei para analisar se o algoritmo acima funciona. Estou apenas
explicando o que e problematico e o que o problema requer. Muito
provavelmente ha um algoritmo otimo para a questao, que e trivial.
Um abraco a Todos
Paulo Santa Rita
4,1958,140802
From: Eduardo Casagrande Stabel [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Subject: [obm-l] Tradução de Problema
Date: Wed, 14 Aug 2002 18:15:53 -0300
Olá pessoal da lista,
alguém sabe como eu devo interpretar o seguinte problema?
Isabel tem dois baralhos, cada um com 50 cartas. Em cada um dos baralhos
estão escritos os números de 1 a 100 (em cada carta estão escritos dois
números, um em cada face da carta). Por um defeito de fabricação, a
distribuição dos números nas cartas não é a mesma nos dois baralhos (por
exemplo, em um dos baralhos o 1 aparece na mesma carta do 2; no outro, o
1
aparece com o 76). Mostre como Isabel deve fazer para que, ao colocar as
100
cartas sobre uma mesa, as faces voltadas para cima mostrem todos os
números
de 1 a 100.
Eu não entendi o que precisa ser mostrado, para mim não está nada claro
sob
que condições ela pode colocar as cartas na mesa, alguém sabe?
Valeu!
Eduardo.
Porto Alegre, RS.
PS. caiu na obm de 2000, fase 3, níveis 1 e 2.
[obm-l] Re: [obm-l] questão IME
O que vc quer é o mesmo que provar que k = k^5 (mod 10) O teorema de Euler diz que a^phi(n) = 1 (mod n) com n=10 temos a^phi(10) = 1 (mod 10) phi(10) = 10.(1/2).(4/5) = 4 portanto a^4 = 1 (mod 10) ou simplesmente k^4 = 1 (mod 10) multiplicando ambos os lados por k obtemos k^5 = k (mod 10) que é o que queríamos demonstrar Até mais Vinicius Fortuna - Original Message - From: rafaelc.l [EMAIL PROTECTED] Subject: [obm-l] questão IME Por favor, me ajudem a resolver a questão abaixo que caiu no IME. Provar que para qualquer numero inteiro k, os números k e k^5 terminam sempre com o mesmo algarismo das unidades. = 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 O administrador desta lista é [EMAIL PROTECTED] =
[obm-l] Re: [obm-l] questão IME
Ops! Uma correção abaixo - Original Message - From: Vinicius José Fortuna [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, August 10, 2002 6:47 PM Subject: Re: [obm-l] questão IME O que vc quer é o mesmo que provar que k = k^5 (mod 10) O teorema de Euler diz que a^phi(n) = 1 (mod n) para todo 'a' primo relativo a n (Sempre esqueço isso) com n=10 temos a^phi(10) = 1 (mod 10) Se 'a' não divisível por 2 ou 5 phi(10) = 10.(1/2).(4/5) = 4 portanto a^4 = 1 (mod 10) ou simplesmente k^4 = 1 (mod 10) para k não divisível por 2 ou 5 multiplicando ambos os lados por k obtemos k^5 = k (mod 10) que é o que queríamos demonstrar Bom, acabou faltando os casos para k=2p ou k=5p Resolvendo esses casos acaba ficando mais complicado que as outras soluções que apareceram aí :-( Até mais Vinicius Fortuna - Original Message - From: rafaelc.l [EMAIL PROTECTED] Subject: [obm-l] questão IME Por favor, me ajudem a resolver a questão abaixo que caiu no IME. Provar que para qualquer numero inteiro k, os números k e k^5 terminam sempre com o mesmo algarismo das unidades. = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] mais uma!
Foi mal, interpretei mal a questão. Li uma hora e resolvi em outra sem lê-la novamente. Acho que é do jeito que vc disse mesmo. De qquer forma dá para resolver da mesma maneira que eu fiz no outro, é só mudar as adjacências entre os vértices no grafo da modelagem que usei. Assim encontrei que a melhor solução é de fato com 9 segundos, que tb pode ser: 1 - 7 - 49 - 48 - 47 - 46 - 45 - 44 - 290 - 2000 290 = 44 + 41*6 2000 = 290 + 285*6 A propósito, tb encontrei pelo programaque o mínimo para ir de 6 a 25 é em 6 movimentos. Até mais Vinicius Fortuna On Sat, 3 Aug 2002, David Turchick wrote: Vc poderia me explicar como que vai de 5 p/ 25 em apenas um segundo? Devo estar interpretando o problema diferente, ou erroneamente. Valeu, David = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] mais uma!
On Sat, 3 Aug 2002, David Turchick wrote:
Para ir de 6 amebas para 25 amebas o mais rápido possível, vc pode tanto
fazer:
6 - 5 - 4 - 28 - 27 - 26 - 25, como
6 - 30 - 29 - 28 - 27 - 26 - 25, e ambas são feitas no menor tempo
possível. (Não provei, mas acho que dá p/ entender o que eu tô fazendo,
tendo pensado um pouquinho no problema. Caso contrário, diga.)
Falso!
De 6 para 25 é possível fazer:
6 - 5 - 25
Quanto ao problema original, esse exemplo mostra que multiplicar sempre
por 7 e não utilizar outros valores pode não levar ao tempo mínimo.
Ao meu ver entendi o problema pela seguite recorrência:
T(1) = 0
T(n) = min(T(n+1), min{2=i=7 e i divide n}(T(n/i))
Como a minha área é programação, implementei um programa que encontrasse o
valor de T(2000). Modelei o problema como caminho mínimo em um grafo
orientado, onde os vértices são os números e as arestas (a,b) ligam
vértices a e b se b=a-1 ou b=a*i, 2=i=7.
O número de movimentos para chegar ao número n será a distância do 1 até
o número.
Assim, encontrei que a solúção mínima é de cinco movimentos, que podem
ser:
1 - 4 - 16 - 80 - 400 - 2000
Até mais
Vinicius Fortuna
Ciência da Computação - Unicamp
=
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
O administrador desta lista é [EMAIL PROTECTED]
=
RE: [obm-l] problemas
Essa letra (a) é falsa de qquer forma. O terceiro plano pode ser paralelo aos outros dois, então a intersecção seria vazia. Vinicius Fortuna On Wed, 31 Jul 2002, Ralph Teixeira wrote: 2.Qual das proposições abaixo é falsa? a) As intersecções de dois planos paralelos, com um tereciro plano,são retas paralelas. Isso já é falso, pois não se sabe se o terceiro plano é distinto dos outros dois. David b) Se dois planos distintos são paralelos, toda reta contida em um deles é paralela ao outro plano. c) Um plano B , paralelo a outro plano X por um ponto x não pertencente a X, é único. d) dois planos distintos paralelos a um terceiro são paralelos entre si. e) se dois planos sÃo paralelos, toda reta paralela a um deles é paralela ao outro. Hmmm... Complementando o que o Morgado falou, eu escolheria (e) como falsa. Afinal, a tal reta pode PERTENCER ao outro plano. Acho isso mais significativo do que o possivel erro em (a). = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] Um Algoritmo Legal
Olá Paulo, O melhor algoritmo que se pode obter para esse problema é O(NxP), já que se gasta isso só para ler a matriz e procurar a minhoca (cuja posição inicial não é dada diretamente). Dessa forma descreverei um algoritmo com tal complexidade. Podemos visualizar o tabuleiro como um grafo onde há um nó para cada casa com valor 1 ou 2. Há arestas entre dois nós se e somente se um nó é adjacente ao outro, o que significa que podemos alcançar um a partir do outro por um único movimento da minhoca. Temos então um problema de caminho mínimo em grafo não direcionado com arestas de peso 1. Podemos então usar uma busca em largura que, em um grafo, o tempo é O(n+m), onde n é o número de nós e m o número de arestas. Como n é O(NxP) e m é (8n)/2, portanto tb O(NxP), temos que a busca em largura funciona em O(NxP). Como funciona? Marcamos todos os nós como não visitados, exceto onde está a minhoca, cuja distância a ela mesma é zero: .#.#.#.#.#.###..##..###.0.#..#...##...#..#### : casa com brasa . casa não visitada Número : distância à minhoca Colocamos a posição inicial em uma lista L . Repetimos então, até visitarmos uma casa da borda, os seguintes passos: início Se a lista L é vazia, termina o programa sem solução Para cada elemento p da lista L: Para cada vizinho f de p não brasa e não visitado Marque f com1 maiso valor de p Coloque f em uma nova lista NL Substitua a lista L pela nova lista NL fim Se terminarmos alcançando uma casa da borda, o valor dessa casa será a solução. Por exemplo: Na primeira execução teremos: .#.#.#.#.#.###.1##..###101#..#...##111#..### Nasegunda execução teremos: .#2#2#.#.#.###21##2.###...2101#..#...##1112...#...222### E o programa terminará com a solução 2. Um abraço Vinicius Fortuna - Original Message - From: "Paulo Santa Rita" [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Thursday, July 04, 2002 5:10 PM Subject: [obm-l] Um Algoritmo Legal Ola Pessoal, Segue abaixo a traducao de um problema de computacao que recebi de outra lista e que achei interessante e digno de figurar nesta nostra lista OBM-L. O Algoritmo e de IA. Uma minhoca esta em uma celula de um labirinto quadriculado NxP ( N linhas, P colunas ). Ela almeja sair do labirinto. Todavia, sabe-se que nalgumas celulas ha brasa, noutras, terra. A minhoca se movimenta como o rei em um tabuleiro de xadrex. Os dados de entrada sao : N ,P e LAB(N,P). LAB(N,P) uma matriz da forma : 0 (zero) - casa com brasa 1 (um) - casa com terra 2 (dois) - a minhoca Exemplo : 101010101010 001100110001 21011011 10011101 1000 O programa ( function ) deve devolver : 1) 0 ( zero ) se nao houver um caminho de saida 2) N ( numero inteiro positivo ) se houver. Neste caso N e o menor numero de passos que a minhoca deve dar para sair do labirinto sem se queimar. O programa pode estar em qualquer linguagem padrao ou em pseudo-codigo. OBS : O tempo de resposta ( inteligencia do algoritmo ) sera o principal fator na classifucacao final dos algoritmos. Um Abraco a Todos Paulo Santa Rita 5,1709,040702
Re: [obm-l] Axiomas de Peano
Ops, faltou uma correção no axioma D. Deveria ser:
D) Se um subconjunto X contido em N é tal que 1 pertence a N e s(X) está
contido em X então X=N
- Original Message -
From: Vinicius José Fortuna [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Sent: Tuesday, June 18, 2002 3:29 PM
Subject: [obm-l] Axiomas de Peano
Na Eureka 3, p. 26, há um artigo de Elon Lages Lima chamado O Princípio
da
Indução, onde o autor afirma que o conjunto N dos números naturais é
caracterizado pelas seguintes propriedades:
A) Existe função s: N - N, que associa a cada n pertencente a N um
elemento
s(n) pertecente a N, chamado o sucessor de n.
B) A função s: N- N é injetiva.
C) Existe um único elemento 1 no conjunto N, tal que 1 != s(n) para todo n
pertencente a N.
D) Se um subconjunto X contido em N é tal que 1 pertence a N e s(X) está
contido em X.
As afirmações A, B, C e D são os axiomas de Peano.
Agora vem a minha dúvida. Imagine o conjunto de números:
V = {0, 1, 2, 3, ...} U {a}, onde o elemento 'a' não pertence a {0, 1, 2,
3,
...}
e a função injetiva s: V - V onde:
s(x) = a, se x=a; senão s(x) = x+1
Temos, então, o conjunto V e a função s que satisfazem os axiomas de
Peano.
Dessa forma, podemos dizer que V é o conjunto dos número naturais, mas não
é!
Qual o problema aí???
Alguém pode esclarecer a minha dúvida?
Obrigado
Vinicius Fortuna
=
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
O administrador desta lista é [EMAIL PROTECTED]
=
[obm-l] Iberoamericana Universitária
Pessoal, Como é que se faz para participar da Olimpíada Iberoamericana de Matemática? Quando vai ser? Mandei um e-mail lá para a OBM perguntando, mas não me responderam. :-( Obrigado Vinicius Fortuna = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] integral sem fazer a conta
Oi Augusto,
Essa notação é a mesma utilizada na linguagem
LaTeXpara redação de textos científicos. Com o uso a gente acaba se
acostumando, mas mesmo assim nem sempre é fácil vizualizar claramente a
expressão de primeira.
Perceba que termos precedidos de um '\' são macros
especiais. No caso, \int seria integral e \frac fração. O que vem seguinto em {}
são parâmetros para a macro, no caso, apenas para o \frac. Termos antecedidos
por '_' são subscritos e precedidos por '^' são sobrescritos. Utiliza-se isso
para os extremos da integral.
Assim podemos ter como exemplo:
P(x) = \sum_{i=0}^n a_i x^i
Como a representação por meio de somatório de um
polinômio de grau n e coeficientes "'a' índice 'i'"
Espero que essa breve explicação facilite o
entendimento de outras fórmulas nesse formato maluco que certamente
virão.
Até mais
Vinicius Fortuna
- Original Message -
From:
Augusto
César Morgado
To: [EMAIL PROTECTED]
Sent: Wednesday, June 05, 2002 8:27
PM
Subject: Re: [obm-l] integral sem fazer a
conta
Eu, e creio que muitos outros,
quero manifestar minha admiraçao por quem consegue entender alguma coisa
escrita em tao exotica notaçao.Morgadoozorio_loof wrote:
GX8IQU$[EMAIL PROTECTED]
type="cite">Observe que se vc desmembrar aintegral em duas,a primeira será \int_{-1}^1\frac{du}{u^2 + (1-x^2)/x^2} e a outraserá zero (integral de umafunção ímpar no limite simétrico), daíé imediato o resultado procurado.\int_{-1}^1 \frac{du}{u^2 +(1-x^2)/x^2} =2\int_0^1 \frac{du}{u^2 +(1-x^2)/x^2}.[]'sLuiz.
Sauda,c~oes,Alguém poderia me mostrar por que\int_{-1}^1 \frac{(1+u)du}{u^2 +(1-x^2)/x^2} =
2\int_0^1 \frac{du}{u^2 +(1-x^2)/x^2}
sem fazer as contas?Observe as mudanças nos limites daintegral
e no numerador do integrando.Ou me dizer um livro de Cálculo quemostra
isso de maneira geral?Como sempre, \frac{A}{B} = A/B.[]'sLuís
[obm-l] Re: [obm-l] Filosófica...
Veja quantos metros a luz anda em um segundo. Constataremos que a velocidade da luz caiu para a metade do que conhecíamos! Será que essa resposta serviu? Vinicius Fortuna - Original Message - From: Rafael WC [EMAIL PROTECTED] To: OBM [EMAIL PROTECTED] Sent: Friday, April 19, 2002 5:38 PM Subject: [obm-l] Filosófica... Com a informação de que tudo no universo tinha duplicado de tamanho no decorrer da noite passada, como se poderia verificar a veracidade de tal informação? Alguém se arrisca??? Rafael. = Rafael Werneck Cinoto ICQ# 107011599 [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED] http://www.rwcinoto.hpg.com.br/ __ Do You Yahoo!? Yahoo! Tax Center - online filing with TurboTax http://taxes.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 O administrador desta lista é [EMAIL PROTECTED] = = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] Muito Doido!!
Considere m a idade da mãe e f a idade do filho: Resolvemos o sistema: m = f+21 m+6 = 5(f+6) Cuja solução dá f=-3/4 de ano ou seja, -3/4 * 12 meses = - 9 meses Ou seja, resposta c, o pai está fazendo o filho!! :-) Vinicius Fortuna - Original Message - From: [EMAIL PROTECTED] Subject: [obm-l] Muito Doido!! Olá amigos , ai vai um probleminha bastante engraçado : A diferença entre a idade da mãe e a do filho , é de 21 anos , se somarmos 6 a idade da mãe e 6 a idade do filho , a idade da mãe fica cinco vezes maior que a idade do filho .Onde esta o pai do filho dela? a- Fugiu. b-A mãe não conhece o pai. c- Esta fazendo o filho. d- Foi preso porque não pagou a pensão . = 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 O administrador desta lista é [EMAIL PROTECTED] =
[obm-l] Power!
Pessoal, Existe alguma forma fácil de se calcular os 4 primeiros dígitos de a^(a^(a^(...a^a))) (o 'a' aparece n vezes) Sendo que a não é múltiplo de 2 nem de 5 Obrigado Vinicius Fortuna = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] Soma de fatoriais
n! p/ n=20 é múltiplo de 1000. ASsim S= 19! + ... + 97! == 19! (mod 1000) 19! é múltiplo de 1000 e não múltiplo de 1. Então o último algarismo será ( 19!/1000)%10 == 19 * 18 *17 * 16 * 3 * 14 *13 * 12 * 11 * 2 *9 * 7 * 6 * 4 *3 *2 (mod10) == 2 Espero não ter errado conta Até mais [ Vinicius José Fortuna ] [ [EMAIL PROTECTED] ] [ Visite www.viniciusf.cjb.net ] On Fri, 29 Mar 2002, Siberia Olympia wrote: Por favor, Qual é o último algarismo não nulo do número 19! + 20! + 21! + ... + 96! + 97! ? = 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 O administrador desta lista é [EMAIL PROTECTED] = = 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 O administrador desta lista é [EMAIL PROTECTED] =
[obm-l] Re: [obm-l] Re: [obm-l] Fatoração
Como dizia o Rafael que apresentou o problema: Sobre a fatoração x^10 + x^5 + 1, esqueci de falar que os coeficientes devem ser inteiros. Então não poderia ser do jeito que vc mostrou. Até mais Vinicius Fortuna - Original Message - From: Giovanni Gabriel [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Tuesday, March 26, 2002 2:44 PM Subject: [obm-l] Re: [obm-l] Fatoração A fatoração não poderia ser também algo como ? ( x^5 + (1+raiz(-3))/2 ) ( x^5 + (1-raiz(-3))/2 ) Abs, Giovanni = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] Muito Bom.
Achei que omenor númeroseria: 0123450 Peguei os zeros do 10, 20, 30, 40, 50os 1,2,3,4,5 dos 5x e o último 0 do 60 E o maior seria: 9567890 Com os 9 dos 9, 19, 29, 39, 49 e os 5,6,7,8,9 dos 5x mais o 0 do 60 Soma dos algarismos:15+80 = 95 Vinicius Fortuna - Original Message - From: Davidson Estanislau To: obm Sent: Monday, March 25, 2002 10:52 AM Subject: [obm-l] Muito Bom. Caro Luiz, Como existem 111 algarismos, ficaremos somente com 11. Para o menor número: O algarismo inicial, será o 1 e escolhi todos os zeros que vem após. Ficando com: 100 Os 4 últimos algarismos escolhi os menores que existe entre os dois últimos zeros (que corresponde a seqüencia 505152..60). Que são o 1, 2, 3, 4. Ficando com: 1012340. Soma dos algarismos: 11 Para o maior número: O algarismo inicial, será o 9 e escolhi todos os 9 que vem após. Ficando com: 99 Os 4 últimos algarismos foram os 8, intercalando entre os nove já existentes. (observe: 1...9..1819..2829..3839..) Ficando com: 98989898989 Soma dos algarismos: 94 Davidson Estanislau
[obm-l] Logarítimo discreto
Dados P, P=2, B, 2=BP e N, 2=NP, existe uma forma fácil de calcular o menor L não negativo tal que: B^L == N (mod P) ??? Obrigado Vinicius Fortuna = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] corredor
On Fri, 25 Jan 2002, pichurin wrote: Em um corredoe existem 900 armários numerados de 1 a 900.Novecentas pessoas numeradas de 1 a 900 atravessam este corredor ,uma a uma, em ordem crescente de numeração.Cada pessoa deve reverter os armários que sAõ múltiplos de sua numeração.Por exemplo, a pessoa de número 4 deve mexer nor armários 4,8,12,16,20,etc, abrindo aqyeles que estÃo fechados e fechando aqueles que estão abertos.Ao final, quais armários estarão abertos e quais estarão fechados? Um armários só é revertido por uma pessoa se ele for múltiplo dela. Um armário será múltiplo de todos os seus divisores. Então o número de mudanças de estado de cada armário será o número de divisores dele. Se esse número for par, ele estará fechado, se for ímpar ele estará aberto. Considere o armário x fatorado como x= p1^a1 * p2^a2 * ... * pn^an, onde pi é primo. O número de divisores de x será d = (a1+1)*(a2+1)+...+(an+1) Se d == 0 (mod 2), o armário ficará fechado. se d == 1 (mod 2), o armário ficará aberto. d é par se e somente se existe (ai+1) par. Ou seja, um armário fica fechado se e somente se possui um fator primo com potência ímpar na sua fatoração. Será que essa resposta já é o suficiente? Até mais Vinicius = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: [obm-l] Re: Orientação para resolução
Uma maneira mais genérica de fazer esse cálculo seria utilizando divisão e conquista em que a potência é sempre dividida por dois. Assim: (Sempre mod 100) 2^1000 = (2^500)^2 2^500 = (2^250)^2 2^250 = (2^125)^2 2^125 = 2.(2^62)^2 2^62 = (2^31)^2 2^31 = 2.(2^15)^2 2^15 = 2.(2^7)^2 2^7 = 2.(2^3)^2 2^3 = 8 Agora é só substituir de trás pra frente. As contas de quadrado mod 100 ficam fáceis se fizer assim: x = 10a + b x^2 = 100a^2 + 20ab + b^2 x^2 = 20ab + b^2 (mod 100) e 20ab (mod 100) = ((ab mod 10).2 mod 10).10 Processando... 2^7 = 2.64 = 28 2^15 = 2.84 = 68 2^31 = 2.24 = 48 2^62 = 48^2 = 04 2^125 = 2.16 = 32 2^250 = 32^2 = 24 2^500 = 24^2 = 76 2^1000 = 76^2 = 76 Normalmente isso não dá muitas contas. É aproximadamente floor(log(n base 2)) operações de quadrado onde n é o expoente. Até mais Vinicius Fortuna On Mon, 21 Jan 2002 [EMAIL PROTECTED] wrote: Quais são os últimos dois algarismos de 2^1000 ?? Não sei resolver esse tipo de questão, mas como encontrei a resposta certa resolvi mandar a mensagem !! Será que alguém poderia postar uma maneira mais fácil de obter essa resposta ?? obs : as igualdades são todas mod 100 2^10 = 24 (2^10)^100 = 24^100 = (2^3*3)^100 = (2^10)^30*3^100 = 24^30*3^100 = (2^3*3)^30*3^100 = (2^10)^9*3^130 = 24^9*3^130 = (2^3*3)^9*3^130 = 2^27*3^139 = 2^30/8*3^139 = 24^3/8*3^139 = 12^3*3^139 = 4^3*3^142 = 64*3^142 analisando as potencias de 3 mod 100: 3^1=3 3^2=9 3^3=27 3^4=81 3^5=43 3^6=29 3^7=87 3^8=61 3^9=83 3^10=49 3^142*64=49^14*64*9 analisando as potencias de 49 mod 100: 49^1=49 49^2=01 49^3=49 49^4=01 .. 49^14=01 mod 100 assim, temos que : 49^14*64*9 = 64*9 = 76 mod 100 Portanto os últimos dois algarismos de 2^1000 é 76 conferindo : 2^1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376 Mathematicus nascitur, non fit Matemáticos não são feitos, eles nascem -- Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.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 O administrador desta lista é [EMAIL PROTECTED] = -- [ Vinicius José Fortuna ] [ [EMAIL PROTECTED] ] [ Visite www.viniciusf.cjb.net ] = 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 O administrador desta lista é [EMAIL PROTECTED] =
Re: Continuação de(Olá amigos da lista , trago alguns exercícios bons.)
On Thu, 17 Jan 2002 [EMAIL PROTECTED] wrote: 2)Suponha que 1 (um ) naval (símbolo n )seja a medida de um ângulo convexo , menor que um ângulo reto , inscrito em um círculo de raio r , cujos lados determinam , nesse círculo , um arco de comprimento r . Assim sendo , a soma das medidas dos ângulos internos de um triângulo é igual a : Essa é mais fácil que parece. O valor do angulo com vértice na circunferência é metade do comprimento que ele delimita dividido pelo raio. Como o raio delimita uma curva de comprimento r e o raio é r, o angulo vale 1/2 radiano. Ou seja, 2 navais = 1 radiano Como a soma dos angulos internos do triângulo é pi radianos, isso é o mesmo que 2.pi navais! Bom, espero que eu tenha entendido o problema direito Até mais Vinicius José Fortuna
Re: ???
Eu acho que ele quis dizer representar o número como x=a_0 * 3^0 + a_1 * 3^1 + ... + a_n * 3^n, Sendo que a_i só pode ser 0 ou 1 e que a soma dos a_i seja =2. Dessa forma, o dois, por exemplo, não pode ser representado, assim como o cinco e muitos outros números, entre eles, as potências de 3. O problema é esse mesmo? Bom, ainda não pensei na resposta do problema, mas é melhor deixá-lo mais claro primeiro. Até mais! Vinicius Fortuna, rumo à Semana Olímpica. On Tue, 1 Jan 2002, Bruno F. C. Leite wrote: At 01:08 01/01/02 -0200, you wrote: Quantos números de 1 a 1998 podem ser escritos como a soma de duas ou mais potências de 3? Será que eu entendi direito? Tome x natural, com 1=x=1998. Escreva x na base 3, e teremos x=a_0 * 3^0 + a_1 * 3^1 + ... + a_n * 3^n, com a_i = 0, 1 ou 2. Se x não for potência de 3, isso é uma forma de escrever x como soma de 2 ou mais potências de 3. Se x=3^n, com n0, então x=3*3^(n-1). A solução é todos os números, menos 1. outra forma: divida x por 3: x=3a+b=a*3^1+b*3^0... Bruno Leite
Re: Cardinalidade
Ué, eu sempre entendi que a cardinalidade de um conjunto fosse o número de elemento do mesmo. Se dois conjuntos possuem infinitos elementos, eu achava que a cardinalidade fosse a mesma. Alguém tem um conceito mais preciso de cardinalidade? Obrigado Vinicius Fortuna [ Indo para a Semana Olímpica :-) ] On Thu, 27 Dec 2001, Rogerio Fajardo wrote: Olá, colegas da lista, Dados dois conjuntos, A e C, infinitos, com cardinalidade de C maior que de A, é sempre possível achar um conjunto B tal que AxB tem a mesma cardinalidade de C? Todo conjunto infinito A tem a mesma cardinalidade de AxA (como ocorre com N e com R)? Se isso vale, já temos a resposta para a pergunta de cima (considerando B=C e que card(A)card(C)). Rogério _ MSN Photos is the easiest way to share and print your photos: http://photos.msn.com/support/worldwide.aspx
Re: Questão
Ué, Para p=2: (2^1 - 1)/2 = 1/2, que não é inteiro Será que entendi errado?? Pelo exemplo entendi que a fórmula é (2^(p-1)-1)/p. Creio que este seja um problema proposto na Eureka de setembro e a fórmula era assim. Qual o teorema de Euler? Boas festas a todos! Até mais [ Vinicius José Fortuna ] [ [EMAIL PROTECTED] ] [ Visite www.viniciusf.cjb.net ] On Tue, 25 Dec 2001, Henrique Lima Santana wrote: Ae pessoal, deem uma olhada nessa questão ache todos os p, primos, tais que 2^p-1 -1/p seja um quadrado perfeito. ( essa expressão resulta sempre num n° inteiro- pelo teorema de Euler) -- ex: pra p=7 = 2^6 -1/7=9 q eh quadrado perf. valeu Henrique _ Send and receive Hotmail on your mobile device: http://mobile.msn.com
Semana Olímpica
Olá Pessoal, Gostaria de saber se vai ter muita gente do nível universitário na Semana Olímpica. Receio chegar lá e ser o único universitário... Até mais [ Vinicius José Fortuna ] [ [EMAIL PROTECTED] ] [ Visite www.viniciusf.cjb.net ]
Re: Dúvida
On Sat, 22 Dec 2001, Alex Vieira wrote: Olá colegas da lista, Vi no cursinho a seguinte questão: Sejam x, y e z números reais positivos. a) Mostre que (x+1/x)*(y+1/y)*(z+1/z) = 8 Derivando (x+1/x) obtemos (1-1/x^2) igualando a zero: 1-1/x^2 = 0 x^2 = 1 x = 1 Este é o ponto de mínimo para (x+1/x) com valor 2. O mínimo para (x+1/x)*(y+1/y)*(z+1/z) será o produto do mínimo de cada fator, que é 2. Então o mínimo de (x+1/x)*(y+1/y)*(z+1/z) = 2*2*2 = 8 Portanto a expressão é = 8 b) Mostre que, se x*y*z=100, então (x+1)*(y+1)*(z+1) = 80 Essa é fácil: (x+1)*(y+1)*(z+1) = x*y*z + xy + xz + yz + 1 xyz = 100 Como a expressão é maior que 100 então é maior ou igual a 80 Até mais Vinicius
Re: funções e fatorial
On Fri, 14 Dec 2001, gabriel guedes wrote: Ola a todos, estou com algumas duvidas gostaria de qualquer sugestão. 1)escreva n! na forma de um polinomio finito. A propósito, a fórmula de Stirling: sqrt(2.PI.n).(n/e)^n n! sqrt(2.PI.n).(n/e)^n.(1 + 1/(12n-1)) D. E. Knuth, em Art of Computer Programming, Fundamental Algorithms, Vol 1, tb demonstrou uma aproximação para n!: n! ~ sqrt(2.PI.n).(n/e)^n.(1 + 1/(12n) + 1/(288n^2) - 139/(51840n^3) - 571/(2488320n^4) + O(1/n^5)) Bom, acredito que não haja uma forma de um polinômio finito conhecida para representar n!. Esses caras são muito feras e não acharam fórmulas mais simples! :-) Até mais Vinicius
Re: ITA 2002 - Problema 12 - Divergencia entre os cursinhos!
No caso o Anglo provou que o David era o vencedor. Mas se o David é o vencedor, a situação final será (David, Rubinho, Ralf). Essa situação só pode ser alcancada por um número par de inversões. Como foram realizadas um número ímpar de inversões, a situação final deveria ser diferente da sugerida, o que é uma contradição ao argumento do Anglo. Dessa forma, fica provado que não há uma situação final que atenda a todas as restrições do problema, o que indica que o trecho não apresenta uma descrição matematicamente correta. Espero ter sido mais claro Até mais [ Vinicius José Fortuna ] [ [EMAIL PROTECTED] ] [ Visite www.viniciusf.cjb.net ] On Thu, 13 Dec 2001, niski wrote: Ola colegas da lista! Gostaria que os srs escrevessem falassem qual é a resposta mais adequada da questao mais comentada do ITA 2002, já que sei que todos por aqui gostam e sabem muito de matematica. O Curso Anglo dá como gabarito a letra A Os demais cursinhos (ETAPA, Objetivo, Poliedro, Alferes e COC) dão como gabarito a letra E. Irei transcrever o problema ,a solução do Anglo e a solucao do ETAPA. Gostaria de saber da opiniao dos srs. Qual cursinho está correto
Re: limites
On Mon, 10 Dec 2001, Vinicius José Fortuna wrote:
lim (e^2x -1)/x
x-0
Essa eu acho que sei:
lim{x-0} (e^2x - 1)/x =
lim{x-0} (e^2x)/x - 1/x =
lim{x-0} (e^2x)/x
Por L'Hopital (é assim que se escreve?)
= lim{x-0} 2.(e^2x) + 2x.(e^2x) =
= 2
Confere?
OPS! Não confere!
Os meus dois passos intermediários estão errados!
Considere apenas
lim{x-0} (e^2x - 1)/x =
lim{x-0} 2.(e^2x) + 2x.(e^2x) =
= 2
Foi mal
Vinicius
Re: ajuda
On Mon, 10 Dec 2001, Eduardo Azevedo wrote: A área total da esfera é 4(pi)*r^2 o volume (4/3)pi*r^3 De onde vem isso: (volume da interseção)/(volume total) = (área da interseção)/(área total) ?? logo V=[(4/3)pi*r^3]*S/[4(pi)*r^2] V= 1/3 * SR Vinicius
Re: limites
On Mon, 10 Dec 2001, Hugo Iver Vasconcelos Goncalves wrote:
qual o limite das seguintes funções?
lim (cotgx)^(1/lnx)
x- 0
lim (e^2x -1)/x
x-0
Essa eu acho que sei:
lim{x-0} (e^2x - 1)/x =
lim{x-0} (e^2x)/x - 1/x =
lim{x-0} (e^2x)/x
Por L'Hopital (é assim que se escreve?)
= lim{x-0} 2.(e^2x) + 2x.(e^2x) =
= 2
Confere?
Até mais
Vinciius
Re: Teoria dos números
O problema se reduz a verificar a validade da seguinte equação: K^5 mod 10 = K mod 10 onde a mob b é o resto da divisão inteira de a por b. A equação é equivalente a: (K mod 10)^5 mod 10 = K mod 10 Dessa forma testando todos os valores possíveis para (K mod 10) resolve o problema. Para facilitar as contas, (K^5 mod 10) é facilmente calculado da seguinte forma: K^5 mod 10 = (K mod 10).(((K mod 10)^2 mod 10)^2 mod 10) mod 10 Até mais [ Vinicius José Fortuna ] [ [EMAIL PROTECTED] ] [ Visite www.viniciusf.cjb.net ] On Sun, 9 Dec 2001 [EMAIL PROTECTED] wrote: Olá colegas, obrigado pela atenção na questão de potências e, relativo a ela, onde encontro a RPM 26 ? Agora, teve uma questão do IME que um aluno me mostrou e só sei resolver usando o pequeno teorema de Fermat, gostaria de saber se há outra resolução. Trata-se de provar que K e K^5 terminam com o mesmo algarismo para todo K inteiro. Prova-se usando que K^5 - K é divisível por dois e por 5 (onde se usa o pequeno teorema). Acho que pode haver outra resolução pois não acredito que o IME queria cobrar o pequeno teorema de Fermat, ou será possível ? Obrigado pela atenção, Raul
Re: Como simplificar?
O que é um polinômio fatorial e uma antidiferença?
Luis, O que vc quis dizer com 2(i)^{(2)}?
Obrigado
[ Vinicius José Fortuna ]
On Wed, 5 Dec 2001, Luis Lopes wrote:
Sauda,c~oes tri...,
Estas duas somas que apareceram uma em seguida à outra
podem ser resolvidas mecanicamente da seguinte forma:
Seja calcular S_n = \sum_{i=1}^n p(i), onde p(i) é um polinômio
de grau k em i.
Expressamos p(i) em função dos polinômios fatoriais (pf) e achamos
uma antidiferença P(i). Então S_n = P(n+1) - P(1).
Exemplo: 2*3 + 3*5 + 4*7 + 5*9 + 6*11 + ... + (n+1)*(2n+1) =
\sum_{i=1}^n (i+1)(2i+1) = \sum_{i=1}^n p(i)
Expressando p(i) em função dos pf, vem: p(i) = 2(i)^{(2)} + 5i + 1.
Então P(i) é (observe a semelhança da integral): (2/3) (i)^{(3)} + (5/2) (i)^{(2)} +
i.
Calculando P(n+1) - P(1) resulta em (2/3) (n+1)n(n-1) + (5/2) (n+1)n + n + 1 - 0 - 0
- 1 =
(n/6) * (4n^2 + 15n + 17)
[]'s
Luís
Re: ajuda (ERRATA)
On Mon, 3 Dec 2001, Vinicius José Fortuna wrote: Ops!, Cometi alguns equívocos: 2) Qual o 496o termo da sequencia 1,2,2,3,3,3,4,4,4,4,5,5,5,5,5, ...? Nessa sequência, o último número n aparece na posição n(n+1)/2, que é o somatório de 1 a n. Então para descobrirmos o 496o. termo, devemos resolver a inequação: x(x+1)/2 = 496, x0 Isso dá x = 31,5 Portanto o 496o. termo da sequência é 32 Errei as contas. É x=31. Então o 496o. termo é 31. 3) No interior do triângulo ABC, equilátero, existe um ponto P tal que AP = 6, BP = 8 e CP= 10. Determine o perímetro do triângulo ABC. Se eu não me engano, existe um teorema que diz que a soma das distâncias de qquer ponto interior de um triângulo equilátero é constante e igual a 2 x tamamnho do lado. Alguém pode confirmar isso pra mim? Na verdade o teorema que eu estava pensando diz que a soma distâncias de qquer ponto interior a todos os lados é constante e igual à altura. Mas aí não dá para resolver de forma tão direta. :-( Até mais Vinciius
Re: potencias
Isso é verdade sim. É só pegar a representação binária dele! Aliás, todo número natural pode ser representado como soma de potências de qquer outro número natural que não seja o zero. Considere que vc queira encontrar a representação de um número x como somas de potências de b. Vc pode usar o seguinte algoritmo: i - 0 a0 - 0 Enquanto x0 faça : ai - x mod b; x - x/b; i - i+1 Onde x/b é divisão inteira e x mod b é o resto da divisão inteira x/b O resultado são os ai de forma que: x = a0*b^0 + a1*b^1 + a2*b^2 + ... + ai*bi^i + ... + an*b^n [ Vinicius José Fortuna ] [ [EMAIL PROTECTED] ] [ Visite www.viniciusf.cjb.net ] On Tue, 4 Dec 2001, gabriel guedes wrote: Ola amigos da lista , me fizeram a seguinte todo numero Natural pode ser escrito como soma de potencias de base 2, eu não sei responder .Gostaria da ajuda de todos , se alguem ja viu algum trabalho relacionado a issoqualquer coisa mesmo
Re: Programa_para_achar_nºs_primos_...
--- Eleu Lima Natalli [EMAIL PROTECTED] escreveu: Alguem sabe em q site posso baixar o prog q ''caça'' nº primos ? Uma técnica muito utilizada em algoritmos de criptografia RSA para encontrar números primos grandes genéricos (não necessariamente de mersenne e tal) é a seguinte: O número de primos até n, para n grande, é em torno de n/ln(n). Então temos que a probabilidade de um número x ser primo é em torno de 1/ln(x). Então, se queremos um número primo com o tamanho de n, teremos que procurar, em média, aproximadamente ln(n) números aleatórios em torno de n para encontrar um que seja primo. Para cada um dos números gerados, deve-se testar se ele é primo ou não. Normalmente faz-se isso com testes de pseudo-primalidade. Se o algoritmo retorna composto então ele é definitivamente composto. Se ele retorna primo então há uma alta probabilidade de ele ser primos. A vantagem desses algoritmos é que eles são rápidos o suficiente. Além disso, há algoritmos que vc pode repetir várias vezes de forma que a chance de um erro de primalidade seja menor do que um erro de hardware! Um desses algoritmos é o de Miller-Rabin. Você pode adquirir maiores informações no livro Introduction to Algorithms de Cormen, Leiserson e Rivest. Espero ter sido claro o suficiente. Até mais Vinicius Fortuna
Re: ajuda
Estou com 4 problemas que não estou conseguindo resolver, se puderem me ajudar, desde já agradeço Bom, essa mensagem é de outubro, mas acho que ainda vale a pena responder. 1) Qual o número de soluções (x,y) da equação 2^(2x) - 3^(2y) = 55, em que x e y são números inteiros? Essa já responderam na lista. 2) Qual o 496o termo da sequencia 1,2,2,3,3,3,4,4,4,4,5,5,5,5,5, ...? Nessa sequência, o último número n aparece na posição n(n+1)/2, que é o somatório de 1 a n. Então para descobrirmos o 496o. termo, devemos resolver a inequação: x(x+1)/2 = 496, x0 Isso dá x = 31,5 Portanto o 496o. termo da sequência é 32 3) No interior do triângulo ABC, equilátero, existe um ponto P tal que AP = 6, BP = 8 e CP= 10. Determine o perímetro do triângulo ABC. Se eu não me engano, existe um teorema que diz que a soma das distâncias de qquer ponto interior de um triângulo equilátero é constante e igual a 2 x tamamnho do lado. Alguém pode confirmar isso pra mim? Dessa forma ficaria fácil. 2.L = 6+8+10 = 24 = L = 12 Então o perímetro seria 36. Bom, tenho que confirmar o teorema. Faz tempo que eu vi isso e não me lembrou onde que foi. 4) Em que proporção deve-se misturar duas soluções de água oxigenada, uma a 30% e outra a 3% para se obter uma mistura a 12%? Essa é mais simples: 30%.X + 3%.Y = 12%(X+Y) 18%.X = 9%.Y 2.X = Y Ou seja, a proporção é 1:2 Até mais [ Vinicius José Fortuna ] [ [EMAIL PROTECTED] ] [ Visite www.viniciusf.cjb.net ]
