[obm-l] Teoria do Caos Problema P vs. NP
Pessoal, Desculpem-me por não falar as minhas intenções no último problema enviado, mas esqueci. Só queria saber, supondo que aquele número pudesse existir (me refiro ao "0,000...01 é diferente de 0?"), e realmente havia infinitos zeros "antes" do 1. Espero não ter causado problemas. Mas peço que respondam a essa minha pergunta com qualquer tipo deresposta(detalhada ou simples),porém que diga algo sobre e osenglobe de uma forma geral de relação: isso do problema pode ser explicado com aquilo, o problema não pode ser resolvido sem a teoria porque..., a teoria tem tudo a ver com o problema, porque...,entre outros (esses exemplossão só para ilustrar epodem estar errados). - Qual a relação da Teoria do Caos com o Problema P vs. NP? Desculpem qualquer coisae obrigado pela atenção, Ivan Miranda.__Converse com seus amigos em tempo real com o Yahoo! Messenger http://br.download.yahoo.com/messenger/
RE: [obm-l] PROBLEMinha
Caro amigo, só não entendi 2 coisas: Como vc concluiu que s = 3y e resolvendo o sistema todo, econtramos: x=20 y=10 z=40 s=30 Assim, x+y+z+S=100(ok!) z=2/3*(x+z)(oK!) mas, s=3/4(y+z) não confere! De: [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Cópia: Data: Mon, 17 Jan 2005 12:44:51 + Assunto: [Desejados] RE: [obm-l] PROBLEMinha x=numero de alunos que acertaram somente a 1a questao y=numero de alunos que acertaram somente a 2a questao z=numero de alunos que acertaram a 1a e 2a s=numero de alunos que nao acertaram nenhuma x+y=30(I) z=(x+z)*3/3 s=(y+z)*3/4 Daí tiramos que: s=3y z=2x logo x+y+z+s=100 3x+4y=100(II) Resolvendo-se o sistema I e II y=10 e s=30 From: "Fabio" <[EMAIL PROTECTED]> Reply-To: obm-l@mat.puc-rio.br To: "obm"Subject: [obm-l] PROBLEMinha Date: Mon, 17 Jan 2005 01:12:21 - Caros amigos, já interpretei o problemas de maneiras diferentes e não consegui achar a resposta. Alguém pode me ajudar? Valeu. Uma turma com 100 alunos fez um teste com duas questões. Verificou-se na correção que: 1.1) 30 alunos acertaram apenas uma questão; 1.2) entre os que acertaram a primeira questão, 2/3 também acertaram a segunda questão; 1.3) entre os que erraram a primeira questão, 3/4 também erraram a segunda questão; Determine quantos alunos erraram as duas questões a) 15 b) 18 c) 24 d) 28 e) 30 E-mail classificado pelo Identificador de Spam Inteligente. Para alterar a categoria classificada, visite a Central do Assinante Esta mensagem foi verificada pelo E-mail Protegido Terra. Scan engine: McAfee VirusScan / Atualizado em 12/01/2005 / Versão: 4.4.00 - Dat 4419 Proteja o seu e-mail Terra: http://www.emailprotegido.terra.com.br/ _ MSN Hotmail, o maior webmail do Brasil. http://www.hotmail.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 = E-mail classificado pelo Identificador de Spam Inteligente Terra. Para alterar a categoria classificada, visite http://www.terra.com.br/centralunificada/emailprotegido/imail/imail.cgi?+_u=fgb1_l=1,1105966982.9159.23759.cagera.terra.com.br,4087,Des15,Des15 Esta mensagem foi verificada pelo E-mail Protegido Terra. Scan engine: McAfee VirusScan / Atualizado em 12/01/2005 / Versão: 4.4.00 - Dat 4419 Proteja o seu e-mail Terra: http://www.emailprotegido.terra.com.br/
RE: [obm-l] PROBLEMinha
z=(x+z)*3/3 esta errado e: z=(x+z)*2/3 s=(y+z)*3/4 esta errado e: s=(y+s)*3/4 e que eu escrevi em uma folha primeiro e depois eu passei para o computador, se vc fizer o diagrama de baloes, 2 baloes em volta de um quadrado vc visualiza melhor, z é a intercessao, um balao menos a intercessao é x e o outro balao menos a intercessao é y, e o que esta por fora dos baloes é s, que é os que nao acertaram nenhuma questao. Desculpe o incomodo, saulo. From: fgb1 [EMAIL PROTECTED] Reply-To: obm-l@mat.puc-rio.br To: obm-l obm-l@mat.puc-rio.br Subject: RE: [obm-l] PROBLEMinha Date: Tue, 18 Jan 2005 09:53:08 -0300 Caro amigo, só não entendi 2 coisas: Como vc concluiu que s = 3y e resolvendo o sistema todo, econtramos: x=20 y=10 z=40 s=30 Assim, x+y+z+S=100(ok!) z=2/3*(x+z)(oK!) mas, s=3/4(y+z) não confere! De:[EMAIL PROTECTED] Para:obm-l@mat.puc-rio.br Cópia: Data:Mon, 17 Jan 2005 12:44:51 + Assunto:[Desejados] RE: [obm-l] PROBLEMinha x=numero de alunos que acertaram somente a 1a questao y=numero de alunos que acertaram somente a 2a questao z=numero de alunos que acertaram a 1a e 2a s=numero de alunos que nao acertaram nenhuma x+y=30(I) z=(x+z)*3/3 s=(y+z)*3/4 Daí tiramos que: s=3y z=2x logo x+y+z+s=100 3x+4y=100(II) Resolvendo-se o sistema I e II y=10 e s=30 From: Fabio Reply-To: obm-l@mat.puc-rio.br To: obm Subject: [obm-l] PROBLEMinha Date: Mon, 17 Jan 2005 01:12:21 - Caros amigos, já interpretei o problemas de maneiras diferentes e não consegui achar a resposta. Alguém pode me ajudar? Valeu. Uma turma com 100 alunos fez um teste com duas questões. Verificou-se na correção que: 1.1) 30 alunos acertaram apenas uma questão; 1.2) entre os que acertaram a primeira questão, 2/3 também acertaram a segunda questão; 1.3) entre os que erraram a primeira questão, 3/4 também erraram a segunda questão; Determine quantos alunos erraram as duas questões a) 15 b) 18 c) 24 d) 28 e) 30 E-mail classificado pelo Identificador de Spam Inteligente. Para alterar a categoria classificada, visite a Central do Assinante Esta mensagem foi verificada pelo E-mail Protegido Terra. Scan engine: McAfee VirusScan / Atualizado em 12/01/2005 / Versão: 4.4.00 - Dat 4419 Proteja o seu e-mail Terra: http://www.emailprotegido.terra.com.br/ _ MSN Hotmail, o maior webmail do Brasil. http://www.hotmail.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 = E-mail classificado pelo Identificador de Spam Inteligente Terra. Para alterar a categoria classificada, visite http://www.terra.com.br/centralunificada/emailprotegido/imail/imail.cgi?+_u=fgb1_l=1,1105966982.9159.23759.cagera.terra.com.br,4087,Des15,Des15 Esta mensagem foi verificada pelo E-mail Protegido Terra. Scan engine: McAfee VirusScan / Atualizado em 12/01/2005 / Versão: 4.4.00 - Dat 4419 Proteja o seu e-mail Terra: http://www.emailprotegido.terra.com.br/ _ MSN Messenger: converse online com seus amigos . http://messenger.msn.com.br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Problemas em aberto - prob 10
Caro Demetrio, Parece que os únicos contra-exemplos para isso são (A,B,C)=(2^m+1,2^m-1,2), para m=1. Além disso, acho que é possível provar algo bem mais forte (para k grande): P tem pelo menos 2^k-k fatores primos distintos. Isso já é maior que k+1 se k=3. Vamos então provar isso primeiro e depois analisar os casos k=1 e k=2. Vamos usar polinômios ciclotômicos, que são polinômios phi_n(x), indexados pelos inteiros positivos n que aparecem na fatoração de x^n-1: para cada inteiro positivo n, x^n-1=produto(d divide n)(phi_d(x)). Isso define os phi_n(x) por recorrência; temos phi_n(x)=produto(1=k=n,mdc(k,n)=1)(x-e^(2.k.pi.i/n)), donde o grau de phi_n(x) é phi(n) (aqui phi é a função de Euler). Segue da primeira definição, via fatoração, por indução, que, para todo n, phi_n(x) tem coeficientes inteiros e coeficiente líder 1. É possível provar que, para todo n, phi_n(x) é um polinômio irredutível, mas não vamos usar isso aqui. Temos A^c-B^c=B^c.((A/B)^c-1)=B^c.produto(d divide c)(phi_d(A/B))= =produto(d divide c)(B^phi(d).phi_d(A/B)). Como phi_d(x) é um polinômio mônico com coeficientes inteiros de grau phi(d), m_d:=B^phi(d).phi_d(A/B) é inteiro, e produto(d divide c)(m_d)=A^c-B^c (e logo m_d é divisor de A^c-B^c, para todo d divisor de c). Note que c tem 2^k divisores, e assim conseguimos escrever A^c-B^c como produto dos 2^k números m_d. Vamos agora examinar possíveis fatores primos comuns dos m_d. Vejamos primeiramente que se q é um primo que não divide mmc(d,r) então q não pode dividir simultaneamente m_d e m_r (desde que d seja distinto de r). De fato, f(x)=B^d.phi_d(x/B) e g(x)=B^r.phi_r(x/B) são fatores de x^mmc(d,r)-B^mmc(d,r), e se m_d=f(A) e m_r=g(A) são múltiplos de q, A é raiz pelo menos dupla de x^mmc(d,r)-B^mmc(d,r) módulo q (isto é, sobre o corpo Z/qZ), donde é raiz de sua derivada mmc(d,r).x^(mmc(d,r)-1). Como q não divide mmc(d,r), deve dividir A^(mmc(d,r)-1), donde divide A, mas A é primo com B, e logo q não divide d e portanto não pode pode dividir A^d-B^d, absurdo. Isso mostra que se q é um primo que divide dois termos distintos m_d e m_r então q tem que ser um dos divisores n_i de c, e nesse caso n_i deve ser um divisor de d ou de r, donde n_i divide no máximo um termo m_d sem que d seja múltiplo de n_i. Observemos agora que, se q é primo e q não divide r, então phi_(qr)(x)=phi_r(x^q)/phi_r(x), o que pode ser verificado a partir das raízes dos polinômios envolvidos. Se olharmos tudo módulo q (i.e., em Z/qZ[x]), temos phi_r(x^q)=(phi_r(x))^q (pois (x+y)^q=x^q+y^q mod q para quaisquer x,y e n^q=n mod q para n inteiro), donde phi_(qr)(x)=(phi_r(x))^(q-1) módulo q, donde phi_(qr)(x)=0 (mod q) se e só se phi_r(x)=0 (mod q) para todo x em Z/qZ. Em particular, fazendo q=n_i, x=A/B, e usando o fato de c (e logo todos os n_i) ser primo com B, temos que, se n_i não divide d, m_d é divisível por n_i se e só se n_i divide m_(n_i.d). Isso mostra que cada n_i divide no máximo dois termos m_r (para r=d e para r=n_i.d, se existir esse d divisor de c/n_i tal que n_i divide m_d). Assim, como A^c-B^c é produto dos 2^k números m_r, todos maiores que 1, e no máximo k pares desses números têm fator comum, A^c-B^c tem pelo menos 2^k-k fatores primos distintos. (cqd). Se k=1, c=p é primo e, pela prova acima, se A^c-B^c só tem um fator primo, A^c-B^c=A^p-B^p deve ser uma potência de p, e A-B também. Assim, A=B+p^k, e A^p-B^p=(B+p^k)^p-B^p=B^(p-1).p^(k+1) (mod p^(k+2)) se p=3 ou se p=2 e k1. Assim, nesses casos, a maior potência de p que divide A^p-B^p é p^(k+1), donde a maior potência de p que divide (A^p-B^p)/(A-B) é p, e logo A^(p-1)+A^(p-2).b+...+B^(p-1)=(A^p-B^p)/(A-B)=p (pois é uma potência de p), e logo 2^(p-1)=A^(p-1)p, absurdo. Assim, p=2 e k=1, donde A^p-B^p=(B+2)^2-B^2=4(B+1), que é uma potência de 2, donde B=2^m-1 e A=2^m+1, como havíamos dito no começo desta mensagem. Finalmente, se k=2, c=p.q, com pq, A^c-B^c=m_1.m_p.m_q.m_(pq), e, pela prova acima, se tivessemos exatamente 2=2^2-2 fatores primos distintos de A^c-B^c, esses fatores deveriam ser p e q. Assim, A^(pq)-B^(pq) é uma potência de p vezes uma potência de q, e logo (A^(pq)-B^(pq))/(A^p-B^p)=m_q.m_(pq) também é uma potência de p vezes uma potência de q. Se A^p-B^p é múltiplo de p, digamos A^p=B^p+k.p^r, onde p não divide k, A^(pq)-B^(pq)=(B^p+k.p^r)^q-B^(pq)=q.B^p.(k.p^r) (mod p^(2r)), donde é múltiplo de p^r e não de p^(r+1), e logo (A^(pq)-B^(pq))/(A^p-B^p) não é múltiplo de p. Por outro lado, se A^(pq)-B^(pq) é múltiplo de p, e A^p-B^p não é múltiplo de p, A^p/B^p não é 1 módulo p, mas (A^p/B^p)^q é 1 módulo q, donde a ordem módulo p de (A^p/B^p) é q, pois q é primo, mas q não divide phi(p)=p-1 (pois q é maior que p), absurdo. Assim, (A^(pq)-B^(pq))/(A^p-B^p) não é múltiplo de p e logo é uma potência de q. Assim, A^(pq)-B^(pq) é múltiplo de q, e, como A^(pq)=(A^p)^q é congruente a A6p módulo q, assim como B^(pq) é congruente a B^p módulo q, A^p-B^p também é múltiplo de q, digamos A^p=B^p+s.q^r, donde
[obm-l] Sequencias
Ola para todos! Alguem poderia me ajudar nesses? 1) Achar uma sequencia que tenha o intervalo [0,1] comoconjunto dosseus valores de aderencia. 2) Se existem b nao nulo e k natural tq b= x_n = n^k para todo n suficientemente grande entao lim x_n^(1/n) =1. Notacao: x_né a sequencia x(n) =é menor ou igual Um abraco!__Converse com seus amigos em tempo real com o Yahoo! Messenger http://br.download.yahoo.com/messenger/
Re: [obm-l] Problemas em aberto
Caros colegas: Seguem abaixo problemas propostos na lista obm-l desde outubro de 2004 que ainda nao foram resolvidos: []s, Claudio. 28) Seja A = conjunto dos inteiros positivos livres de quadrados e que tem um numero ímpar de fatores primos (distintos, claro!) Assim, A contém todos os primos e seu menor elemento composto é 30 = 2*3*5. Calcule o valor de Soma(n em A) 1/n^2. Pode usar, sem demonstrar, que: Soma(n em N) 1/n^2 = Pi^2/6 e Soma(n em N) 1/n^4 = Pi^4/90. Para s1, por fatoração única e convergência absoluta, soma(n=1 a infinito)(1/n^s)=produto(p primo)(1+1/p^s+1/p^(2s)+...)= =produto(p primo)(1-1/p^s)^(-1) (essa é a popular fórmula de Euler). Por razões análogas, se B = conjunto dos inteiros positivos livres de quadrados e que têm um numero ímpar de fatores primos distintos, soma(n em B)(1/n^2)-soma(n em A)(1/n^2)=produto(p primo)(1-1/p^2)= =(soma(n=1 a infinito)(1/n^2))^(-1)=6/pi^2, enquanto soma(n em B)(1/n^2)+soma(n em A)(1/n^2)=produto(p primo)(1+1/p^2)= =produto(p primo)((1-1/p^4)/(1-1/p^2))=(pi^2/6)/(pi^4/90)=15/pi^2. Assim, soma(n em A)(1/n^2)=(15/pi^2-6/pi^2)/2=9/(2.pi^2)= =0,45594532639051997149745758444377 Abraços, Gugu = 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] AMOSTRAGEM!
Ok! Chicão e demais colegas! Com relação ao problema das duas amostras, muitos participantes relatam a primeira amostragem como mais convincente, por causa da grande preponderância das pedras vermelhas sobre as verdes. Quais são as reais diferenças com que cada amostragem reflete precisamente a cor predominante na urna? As diferenças são de 4 para 1 na primeira. Mas as chances de que a segunda seja mais precisa são muito maiores: 16 para 1. Suponhamos que determinamos a estatura média de uma amostra de 50 estudantes, escolhidos ao acaso, de uma turma de 500 e que tenhamos calculado o erro provável desta média. Suponhamos, também, que calculamos a estatura média dos 50 rapazes mais altos da turma, e seu erro provável. Qual dos erros prováveis é o menor? Pode explicar a razão? Este assunto sobre amostragem me faz lembrar o excelente artigo sobre pesquisa eleitoral do saudoso prof. Flávio Wagner Rodrigues (IN MEMORIAM) no tocante à proporcionalidade entre o tamanho da amostra e a população (RPM-45). Vale salientar que perdi um grande amigo postal, apesar dos incômodos que lhe causei com minhas pegadinhas inconvenientes, aliás, toda a comunidade matemática ficou negativa após sua partida. Eternas saudades e até algum dia, com certeza! Agora, quanto às pegadinhas cunhadas por Sternberg, vocês estão indo bem, pois já conseguiram acertar as duas primeiras... Divirtam-se! __ WebMail UNIFOR - http://www.unifor.br. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
[obm-l] PENSANDO COMO UM ECONOMISTA!
O departamento de produção da National Cabinet Corporation emprega 20 trabalhadores não-especializados, 45 semi-especializados e 60 trabalhadores altamente especializados. Uma análise cuidadosa da produtividade dos três tipos de trabalhadores indica que o produto marginal do trabalhador não-especializado é de 10 unidades por dia de trabalho, o produto marginal do trabalhador semi-especializado é de 20 unidades por dia de trabalho e o produto marginal do trabalhador especializado é de 50 unidades por dia de trabalho. As taxas de salário pagas para cada um dos três tipos de trabalhadores resultam em um custo de $20 por dia para o trabalhador não-especializado, $30 por dia para o trabalhador semi-especializado, e $50 por dia para o trabalhador especializado. A produção encontra-se atualmente no nível desejado pela empresa. Você sugeriria uma mudança na combinação de tipos de trabalho utilizados pelo departamento de produção da empresa? Por que? Afinal! O desconto para idosos é um ato de generosidade ou visa a maximização de lucros? Se o desconto para idosos é válido para a entrada de cinema, então por que ele não vale para a pipoca? Um abraço à todos! __ WebMail UNIFOR - http://www.unifor.br. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
[obm-l] ÁLGEBRAS DE BOOLE!
Em 1938, o matemático americano Claude Shannon percebeu o paralelo entre a lógica proposicional e a lógica de circuitos, e comprendeu que álgebras de Boole poderiam ter um papel importante na sistematização desse novo ramo da eletrônica. De acordo com o teorema sobre álgebras de Boole, qualquer álgebra de Boole finita tem que ter 2^m elementos para algum m. Prove o resultado mais fraco de que nenhuma álgebra de Boole pode ter um número ímpar de elementos. Você é o administrador de uma rede que, atuando em uma região extensa, serve os diversos escritórios de sua companhia espalhados pelo país. As mensagens viajam através da rede roteadas de ponto a ponto até chegarem aos seus destinos. Cada nó na rede, portanto, funciona como uma estação distribuidora, recebendo e enviando mensagens para outros nós de acordo com um roteiro de distribuição mantido em cada nó. Algumas conexões na rede têm tráfego intenso, enquanto outras são menos usadas. A intensidade do tráfego pode variar dependendo da hora do dia; além disso, nós novos podem ser gerados e outros nós podem ser desativados. Portanto, você precisa atualizar periódicamente a informação contida em cada nó, de modo que ele possa transmitir mensagens ao longo do caminho mais eficiente (isto é, o que tem tráfego menos intenso). Como calcular o roteiro de distribuição para cada nó? Abraços! __ WebMail UNIFOR - http://www.unifor.br. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
[obm-l] fisica
responda V ou F: I- numa expansão isotérmica de um gás perfeito sua pressão aumenta. II-numa compressão isobárica sua temperatura aumenta. III-numa expansão adiabática de um gás perfeito sua temperatura absoluta diminui. = 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] fisica
responda V ou F: I- numa expansão isotérmica de um gás perfeito sua pressão aumenta. R: F, isotermica p.v=k, se v aumenta, p diminui, sendo k cte II-numa compressão isobárica sua temperatura aumenta. F, pois se o volume diminui, T diminui tbm. III-numa expansão adiabática de um gás perfeito sua temperatura absoluta diminui. V, pois se o trabALHO EH POSITIVO, A VARIACAO DE ENERGHIA INTERNA EH NEGATIVA,o que eh acarretado porDIMINUICAO DE TEMPERATURA = 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] Equacoes exponenciais...
Pessoal, estou estudando o segundo livro de iezzi, e em meio aos exercicios sobre equacoes exponenciais, alguns metodos de solucoes foram apresentados, como a utilizacao da icognita auxiliar e algumas manipulacoes matematicas (divisão entre termos e colocacao de um termo em evidencia). Eu gostaria de pedir a lista, uma ajuda, em relação a vizualizacao do metodo mais adequado a ser utilizado em uma questao, ou seja, que tipo de necessidade a questao apresenta de modo que direcione a um ou outro metodo? Agradecendo desde ja... Rick P.s: Se possivel, eu gostaria de uma ajuda ao nivel do ensino medio :) = 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 =