Re: Problema Republica Tcheca
-Mensagem original- De: Bruno Leite [EMAIL PROTECTED] Para: [EMAIL PROTECTED] [EMAIL PROTECTED] Data: Quinta-feira, 19 de Julho de 2001 01:47 Assunto: Re: Problema Republica Tcheca -Mensagem original- De: Bruno Leite [EMAIL PROTECTED] Para: [EMAIL PROTECTED] [EMAIL PROTECTED] Data: Quinta-feira, 19 de Julho de 2001 00:46 Assunto: Re: Problema Republica Tcheca Oi Henrique Vamos definir a função g:N-N, mais natural e mais fácil de se lidar, da seguinte forma: g(n)=k pra todo inteiro com n =2^k*l , onde k eh um numero natural e l eh impar. veja que ela é quase igual a função f, só diferindo nos ímpares (f(impar)=1 e g(impar)=0). Agora vamos calcular os valores iniciais de g e dispo-los de uma forma diferente. Considere a árvore abaixo: g(2) g(3) g(4) g(5) g(6) g(7)g(8) g(9) g(10) g(11) g(12) g(13) g(14) g(15) g(16) Cada linha tem 2^(n-1) elementos. Vamos dizer que g(2) é pai de g(3) e g(4), assim como g(5) é pai de g(9) e g(10) e g(8) é pai de g(15) e g(16). de modo geral, g(n) é pai de g(2n-1) e g(2n). Substituindo pelos valores de g: 1 0 2 01 03 0 1 0 2 0 1 0 4 É fácil ver e provar que se g(n)=k, então os filhos de g(n) valem 0 e k+1. A partir daí vc sabe dizer quanto dá a soma de cada linha? Não vou terminar o problema por preguiça e porque tenho certeza que agora não falta muito, até porque é fácil relacionar as somas de f com as de g... Não sei se eu fui claro, então vou dar uma consertada. A soma da i-esima linha da arvore da função g é 2^(i-1) (indução) Então a soma das linas da arvore até a linha k é 1+2+4+...+2^(k-1)=2^k -1 Se fizéssemos a arvore de f em vez de g, todos os zeros virariam uns. Então a soma até a linha k é 2^k + 2^(k-1) - 1, pois há 2^(k-1) zeros até a linha k ( vamos lembrar que f(1) não está na árvore, mas é um zero que se converte em um, e deve ser contado) Isso mostra que f(1)+f(2)+...+f(2^k)=2^k + 2^(k-1) - 1 Em particular, f(1)+f(2)+...+f(2^16)=2^16 + 2^15 - 1=98303 Logo sabemos que o n do problema está entre 2^16 e 2^17. Agora só falta somar o começo da linha 17 até dar 123456. Agora não é difícil terminar. Estou vendo **agora** que tem outro modo de se fazer este problema: fixe n. Quantos k, de 1 a n, satisfazem f(k)=1? e f(k)=2? Seja h_i o número de inteiros de 1 a n com f(k)=i. Então f(1)+...+f(n)=h_1 + 2h_2 + 3h_3 +... ( a soma é infinita, mas a partir de um ponto os termos sao todos nulos) Com essa formula em mente podemos achar por tentativa e erro o valor de n pedido. Vou fazer as contas com mais cuidado no papel, mas acredito que isso está certinho. Fui pensar e descobri que esse método acima não é bom. O primero jeito que eu sugeri está correto. Há um terceiro modo. Seja g a função definida lá no começo do email. Sabemos que, para n par, soma(g(k),k=1...n)=[n/2]+[n/4]+[n/8]+[n/16]+...=n/2+[n/4]+[n/8]+[n/16]+... Então, soma(f(k),k=1...n)=n/2+n/2+[n/4]+[n/8]+[n/16]+...=n+[n/4]+[n/8]+[n/16]+... Agora sim, com esta fórmula certamente achamos o n pedido. Seja z(n)=n+[n/4]+[n/8]+[n/16]+... Fazendo umas continhas, vemos que z(82308)=123457 Logo soma(f(k),k=1...82308)=123457=soma(f(k),k=1...82307)+f(82308)=soma(f(k),k=1. ..82307)+f(82308)= soma(f(k),k=1...82307)+2 Logo soma(f(k),k=1...82307)=123455 e n=82307 Espero que não esteja errado pois mandar um quarto email para consertar as coisas já é muita vergonha... Bruno Bruno Leite [EMAIL PROTECTED] [EMAIL PROTECTED] http://www.ime.usp.br/~brleite Bruno Leite [EMAIL PROTECTED] [EMAIL PROTECTED] http://www.ime.usp.br/~brleite PS Aliás toda a lista de Olimpíadas ao redor do mundo é interessante. Gostaria de saber se alguém sabe fazer o 72. -Mensagem original- De: Henrique Lima [EMAIL PROTECTED] Para: [EMAIL PROTECTED] [EMAIL PROTECTED] Data: Quinta-feira, 19 de Julho de 2001 00:07 Assunto: Problema Republica Tcheca gostaria de ajuda nesse problema Uma função f:N-N é tal q f(n)=1 se n eh ímpar e f(n)=k pra todo inteiro par n =2^k*l , onde k eh um numero natural e l eh impar. determine o maior natural n para o qual: f(1)+f(2)+...+f(n)=123456 valeuz _ Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.
Re: Como provar que E=1/2(mv^2)?
Ha uma maneira de fazer que nao tenho tempo de explicar aqui agora. A ideia eh usar graficos e usar que a area debaixo de um certo grafico (que serah um triangulo) eh metade da base pela altura. No fim de semana eu faco. JP - Original Message - From: Daniel [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Wednesday, July 18, 2001 9:53 PM Subject: Re: Como provar que E=1/2(mv^2)? Bem Gustavo, pessoalmente não conheço nem uma forma de demonstrar a energia cinética de um corpo com física do ens. médio. Você pode comprovar que a fórmula é verdadeira pelo uso da análise dimensional. Pelo que sei 1/2(mv2) é um caso particular da teoria da relatividade restrita, quando as velocidades são muito pequenas em comparação com a velocidade da luz, mas isso escapa ao ens. médio infelizmente. Quanto aos melhores livros para o ens. médio indico a coleção Tópicos de Fisíca, editora saraiva, autor Ricardo Helou Doca. É um pouco cara mais possui excelente teoria e exercícios. Daniel
Re: Como provar que E=1/2(mv^2)?
Pelo que sei 1/2(mv2) é um caso particular da teoria da relatividade restrita, quando as velocidades são muito pequenas em comparação com a velocidade da luz, mas isso escapa ao ens. médio infelizmente. Eu acho que dá pra aprender relatividade restrita tranquilamente com a matematica do ensino médio. Ainda mais para pessoas que já estão acostumadas a estudar para todas as olimpíadas... É claro que, quanto mais avançada for a sua matemática, mais elegante e simples vai ficar a relatividade restrita (e qualquer outra teoria fisica), mas a matematica do ensino medio não impede que se deduzam os fenomenos preditos pela relatividade restrita. Até mais... Bruno
Re: Como provar que E=1/2(mv^2)?
Ha uma maneira de fazer que nao tenho tempo de explicar aqui agora. A ideia eh usar graficos e usar que a area debaixo de um certo grafico (que serah um triangulo) eh metade da base pela altura. No fim de semana eu faco. O grafico da velocidade em função do tempo num movimento uniformemente acelerado será um trapezio (um triangulo se voce assumir velocidade inicial 0 para facilitar) e voce terá duas equações: 1) v = v0 + a.t 2) s - s0 = (v + v0).t / 2 Isolando o tempo na primeira equação e substituindo na segunda, obtem-se a equação: 3a) v^2 = (v0)^2 + 2.a.(s-s0) Multiplicando por m/2: 3b) (mv^2)/2 = [m(v0)^2]/2 + F . (s-s0) Agora é só uma questão de olhar pra equação e dar nomes aos termos que apareceram: Energia Cinetica e Trabalho da força F. Talvez não seja uma questão de provar a expressão para energia cinetica, mas sim de simplesmente dar um nome a essa expressão matemática. Experimentalmente tem-se verificado que uma certa coisa tem se conservado em todos os experimentos feitos até hoje. Deu-se então o nome de energia para essa coisa. Nas diversas teorias que explicam esses experimentos, essa coisa aparece como uma soma de vários termos, que receberam nomes como: Energia Cinética, Potencial, de massa de repouso... Essa é a minha atual ideia a respeito do conceito de energia, que com certeza é bastante pessoal. Até mais... PS: Quão Off-topic é discutir energia cinética na lista da OBM? Bruno Woltzenlogel Paleo
Re: sokoban
Ola Pessoal, Para efeitos de contraditorio e para que o colega Niski, que propos a questao, nao se sinta desistimulado em sua louvavel pretensao de formalizar o jogo de sokoban, e importante que se registre que o interesse em encontrar um algoritmo para o jogo nao esta, a principio, preocupado com aspectos operacionais ... Para a Tecnologia e a para a Pratica as questoes de tempo, eficiencia e eficacia sao fundamentais e irremediaveis, isto e, em qualquer projeto e fundamental provar que ele, alem de bom e correto, seja tambem viavel nas dimensoes do tempo ( vamos gastar um tempo bem finito para realiza-lo ? ) e das financas ( Ha dinheiro suficiente pra realiza-lo ? ) Nao me parece que estes aspectos operacionais sejam relevantes em um estudo teorico. Sao, sim, nesta dimensao pura e teorica, aspectos de somenos importancia ... Hoje nos sabemos, pela teoria Teoria da Relatividade Geral, que podemos causar efeitos temporais sensacionais, tais como aqueles expressos no paradoxo do gemeos. Nao ha ainda tecnologia para implementa-los : significa que devemos abandonar tais estudos simplesmente porque eles sao , atualmente, operacionalmente irrealizaveis ? Evidentemente que nao ! E o imaginario dos homens que cria a praxis do futuro, assim dizia Gaston Bachelar ! Se o algoritmo do jogo sokoban que viermos a achar seja de natureza exponencial ( cresce muito rapido ) ou polinomial ( cresce mais lentamente ) e irrelevante, na dimensao de discussao teorica em que nos encontramos. E inclusive irrelevante se vamos ou nao achar um algoritmo ... O investimento da inteligencia em investigar e por si so compensador e louvavel, independente dos resultados praticos que dai promanem ! Por outro lado, e evidentemente falso e TALVEZ uma demonstracao de pura prepotencia avaliarmos que qualquer outra(s) mente(s) diferente da nossa nao possa encontrar algo melhor do que aquilo que conseguimos fazer e que ja conhecemos : Se aquilo que eu conheco e consigo fazer e so forca bruta DEVO CONCLUIR que MUITO PROVAVELMENTE alguma outra inteligencia podera e devera encontrar algo melhor que isso ... Nao o contrario : Pois e isso que a historia da ciencia vem demonstrando acontecer ao longo dos seculos ! Considere o seguinte problema : Existe um algoritmo que recebe uma equacao diofantina generica e devolve sim, caso ela tenha uma solucao no anel dos inteiros, ou nao, no caso contrario ? Um Matematico Russo provou que nao existe um tal algoritmo. Significa, portanto, que jamais existira um programa de computador que implemente este algoritmo, em tempo polinomial ou nao, qualquer que seja a linguagem. Nao devemos, portanto, nunca mais estudar quaisquer equacoes diofantinas ... Ah, eu ia esquecendo ... Nem toda Matematica cabe no copinho da teoria de computacao ... Um abraco Paulo Santa Rita 5,1337,19072001 From: Fábio Dias Moreira [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: sokoban Date: Thu, 19 Jul 2001 01:38:23 -0300 -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Em Qua 18 Jul 2001 09:40, Paulo Santa Rita escreveu: [snip] DIAGRAMA DE UMA ESTRATEGIA Uma estrategia pode ser descrita assim ( vou imaginar duas caixas e um motor ) [snip] Evidentemente que o problema ainda esta longe de ser resolvido, mas ja temos alguns instrumentos matematicos que podem descreve-los. Nao sei se sao os melhores, mas e um comeco. E entao, eu dei o passe : voce agora faz o gol ? Vou adicionar aqui que, provavelmente, qualquer algoritmo que resolve um jogo de Sokoban não deve ser muito melhor que força bruta. O site [URL: http://web.cs.ualberta.ca/~joe/Preprints/Sokoban/paper.html] prova que é possível simular uma máquina de Turing com o jogo de Sokoban. Em particular, é possível implementar um problema NP-completo. Como os problemas NP-completos levam tempo exponencial (pelo menos com os melhores algoritmos conhecidos), resolver um jogo de Sokoban também deve levar tempo exponencial (a não ser que vcs encontrem um algoritmo esperto o bastante, o que implica num algoritmo melhor para resolver problemas NP-completos). Em particular, se vcs encontrarem um algoritmo que rode em tempo polinomial, vcs podem se considerar donos de um milhão de dólares :) [URL: http://www.claymath.org/prizeproblems/statement.htm] [URL: http://www.claymath.org/prizeproblems/pvsnp.htm]. []s, - - Fabio Dias ([EMAIL PROTECTED], ICQ# 31136103) RPG em Revista: A sua revista virtual de RPG! http://www.rpgemrevista.f2s.com/ -BEGIN PGP SIGNATURE- Version: GnuPG v1.0.6 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE7VmRJW7XDIUgHE2YRAgsMAKCVdHh7zL6x3Sim9BDe3NfSoM77wgCdGrpq 3B/ekH7e1ltTA05a7Ma66nA= =Yz4k -END PGP SIGNATURE- _ Seja avisado de novas mensagens do
Re: Como provar que E=1/2(mv^2)?
O que precisa ser verificado experimentalmente ou demonstrado (a partir das leis de Newton ou algum outro conjunto de leis tomadas como 'axiomas') é que existe conservação de energia. Para que isso faça sentido é preciso definir outras formas de energia (por exemplo, a energia potencial de um campo gravitacional) Eu até acho que o principio da conservação de energia não pode ser desprovado. Sempre que algum fenomeno parece contrariar a conservação, nós inventamos, definimos, uma nova forma de energia: Quando um corpo cai, partindo do repouso, sua energia cinetica está aumentando, não está sendo conservada. Então nós pegamos e inventamos a energia potencial gravitacional para restaurar o nosso principio... e assim por diante. As coisas começam a ficar estranhas e interessantes na teoria da relatividade, já que todas essas energias, definidas simplesmente para facilitar alguns calculos (através da conservação de uma certa quantidade associada a um sistema), passam, por E=mc^2, a ter uma influência mais ativa no sistema. As energias potenciais (antes meros artificios) passam a ter peso, são atraidas gravitacionalmente. Mas isso exige que descubramos uma resposta para a seguinte pergunta: Onde estao localizadas essas energias potenciais? O que nos leva a necessidade de um conceito de densidade de energia... (Estou fortemente desconfiado que o conceito de densidade de energia é inconsistente com qualquer teoria que trate a força gravitacional como uma força comum, como na teoria newtoniana ou como a força eletrostatica. Sendo assim, o conceito de densidade de energia exigiria uma nova teoria de gravitação, como a relatividade geral com seu espaço-tempo curvo... Mas eu ainda não estudei relatividade o suficiente...) Até mais... Bruno Woltzenlogel Paleo
Re: O próximo número é ...
Na minha opinião, qualquer número que você colocar serve. Esse tipo de questão não é muito preciso. Mesmo se fosse 2,4,6,8,10,...qual o próximo termo? Poderia ser 12 ou raiz(77) ou qualquer coisa! Tenho certeza que, dados uns termos iniciais de uma sequência, pode-se arrumar umas 3 ou 4 regras distintas que nos forneçam 3 ou quatro respotas com alguma lógica. Por exemplo, poderíamos completar 2,4,6,8,10 como 2,4,6,8,10,10,8,6,4,2,2,4,6,8,10,10,8,6,4,2... ou 2,4,6,8,10,20,40,60,80,100,200,400,600,800,1000... ou 2,4,6,8,10,4,6,8,10,12,6,8,10,12,14... ou sei lá... Ainda poderíamos fazer interpolação polinomial com os dados! Todas essas têm um certo padrão. Bruno Leite [EMAIL PROTECTED] [EMAIL PROTECTED] http://www.ime.usp.br/~brleite -Mensagem original- De: [EMAIL PROTECTED] [EMAIL PROTECTED] Para: [EMAIL PROTECTED] [EMAIL PROTECTED] Data: Quinta-feira, 19 de Julho de 2001 15:50 Assunto: O próximo número é ... Olá a todos, Será que alguém pode me ajudar com essa ? Tem-se a seguinte seqüência: 80, 84, 72, 27. Sabe-se que os termos dessa seqüência não foram postos ao acaso e, portanto, há uma regra que indica o próximo termo da progressão. Sabendo-se que esta regra se baseia em conceitos aritméticos, diga qual o próximo termo dessa seqüência. a-) 97 b-) 81 c-) -81 d-) -97 e-) 91 Obrigado pela atenção. Abraços, Raul
Re: Como provar que E=1/2(mv^2)?
Quando estudei estas coisas, tive uma impressao semelhante ... me parecia que tudo era uma questao de convencao. Existia alguma coisa que resolveram chamar de energia cinetica e se expressava matematicamente ( era quantificada ) pela equacao mv^2/2. Mas, afinal, o que energia cinetica ? Eu sabia calcular a quantidade de energia cinetica, mas achava que tambem deveria ser capaz de ver intelectual essa substancia se manifestanto nos fenomenos. Situacao semelhante ocorre com o momento linear : mv. Legal saber que eu também não fui o único a ter essas impressões. Comecei a estudar física a cinco anos atrás no ensino médio e desde então vivo numa contínua guerra tentando construir para mim mesmo um conceito mais real, mais físico, de energia. A atual batalha em que me encontro é a do paradoxo da densidade de energia que descrevi no outro e-mail. O momentum linear sempre foi mais natural para mim... Leibniz argumentava que o verdadeiro efeito de uma forca era a variacao da forca viva ( igual a Mv^2), enquanto Newton achava que o verdadeiro efeito da forca se media pela variacao da quantidade de movimento ( mv ). O que eles queriam dizer com verdadeiro efeito? Em sintese : o sentimento que voce expressa eu ( e acredito que muitos outros ) o conheco muito bem. Digamos que so vim entender sentir o que vem a ser energia apos ler os artigos que mencionei e acompanhar detidamente as experiencias de joule que provam que calor e energia. Esse chavao ( calor e energia ) e errado. O que joule mostrou e que o calor medido pode ser associado a grandeza mv^2/2. Esse assunto de Joule me lembrou de uma situação que deve se repetir em outras escolas de ensino médio: O professor de física definir Temperatura como sendo o grau de agitação térmica da substancia. Qual a utilidade de uma definição não-operacional (que não ensina a medir) como essa? Existem maneiras simplificadas de mostrar a relação da temperatura com a energia cinética média das particulas. Por que os professores não as mostram? Preguiça ou alguma crença na incapacidade de aprendizado dos alunos? Essa definição de temperatura é comparavel àquela de alguns professores de matematica definirem a reta como um circulo de raio infinito... Até o futuro. Bruno Woltzenlogel Paleo
Re: Como provar que E=1/2(mv^2)?
E aí Bruno, também penso sobre estas questões. Já que somos muito matemáticos fica muito complicado aceitarmos tais propriedades. Uma pessoa que discutiu muito para explicar o que é energia foi Feynman. Talvez vc encontre algo na net. Ats, Marcos Eike - Original Message - From: Bruno Woltzenlogel Paleo [EMAIL PROTECTED] To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED]; [EMAIL PROTECTED] Sent: Thursday, July 19, 2001 5:14 PM Subject: Re: Como provar que E=1/2(mv^2)? Quando estudei estas coisas, tive uma impressao semelhante ... me parecia que tudo era uma questao de convencao. Existia alguma coisa que resolveram chamar de energia cinetica e se expressava matematicamente ( era quantificada ) pela equacao mv^2/2. Mas, afinal, o que energia cinetica ? Eu sabia calcular a quantidade de energia cinetica, mas achava que tambem deveria ser capaz de ver intelectual essa substancia se manifestanto nos fenomenos. Situacao semelhante ocorre com o momento linear : mv. Legal saber que eu também não fui o único a ter essas impressões. Comecei a estudar física a cinco anos atrás no ensino médio e desde então vivo numa contínua guerra tentando construir para mim mesmo um conceito mais real, mais físico, de energia. A atual batalha em que me encontro é a do paradoxo da densidade de energia que descrevi no outro e-mail. O momentum linear sempre foi mais natural para mim... Leibniz argumentava que o verdadeiro efeito de uma forca era a variacao da forca viva ( igual a Mv^2), enquanto Newton achava que o verdadeiro efeito da forca se media pela variacao da quantidade de movimento ( mv ). O que eles queriam dizer com verdadeiro efeito? Em sintese : o sentimento que voce expressa eu ( e acredito que muitos outros ) o conheco muito bem. Digamos que so vim entender sentir o que vem a ser energia apos ler os artigos que mencionei e acompanhar detidamente as experiencias de joule que provam que calor e energia. Esse chavao ( calor e energia ) e errado. O que joule mostrou e que o calor medido pode ser associado a grandeza mv^2/2. Esse assunto de Joule me lembrou de uma situação que deve se repetir em outras escolas de ensino médio: O professor de física definir Temperatura como sendo o grau de agitação térmica da substancia. Qual a utilidade de uma definição não-operacional (que não ensina a medir) como essa? Existem maneiras simplificadas de mostrar a relação da temperatura com a energia cinética média das particulas. Por que os professores não as mostram? Preguiça ou alguma crença na incapacidade de aprendizado dos alunos? Essa definição de temperatura é comparavel àquela de alguns professores de matematica definirem a reta como um circulo de raio infinito... Até o futuro. Bruno Woltzenlogel Paleo