Re: [obm-l] Moedas em sacos
Olá, Não sei se meu raciocínio está correto, mas eu pensei em resolver o problema da seguinte forma: Como sabemos que o saco é mais pesado, para a última medição (terceira), no pior caso, devemos ter 3 sacos. Mediríamos dois deles na balança, e se um for mais pesado, é este; se ambos forem iguais, o terceiro é o saco mais pesado. Dito isso, na segunda (penúltima) medição, devemos medir grupos de 3 sacos. Podemos medir 3 grupos, usando a mesma lógica da última medição. Portanto, deve chegar 9 sacos na segunda medição. Assim, na primeira medição, pelo mesmo raciocínio, teremos 3 grupos de 9 sacos. Portanto, o N máximo é 27. Espero que esteja certo... Beijos, -- -- Fernando Aires [EMAIL PROTECTED] Em tudo Amar e Servir -- On Sat, 12 Feb 2005 10:57:42 -0200, Rogerio Ponce [EMAIL PROTECTED] wrote: Ola' pessoal, Existem N sacos abertos com 10 moedas cada um. Um deles, defeituoso, tem 10 moedas iguais entre si, porem mais pesadas que o padrao. Os outros sacos tem as 10 moedas com o peso padrao (a principio desconhecido). Voce dispoe de uma balanca de 2 pratos, que fornece a diferenca de peso entre os pratos (prato da esquerda menos prato da direita). Qual o maior N que ainda permite a determinacao do saco defeituoso com apenas 3 leituras ? []'s Rogerio Ponce = 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] Moedas em sacos
Acho ki vc pode usar mais informacao que te foi passada no enunciado. 1 - tem 10 moedas por saco. 2 - A balanca te da a diferenca entre os pratos A informacao 2 acima e bastante relevante ja que com uma pesagem podemos saber exatamente quanto a mais cada moeda pesa. Seguindo um raciocinio parecido com o seu cheguei a 126 sacos de moedas possiveis. Vou deixar vc refazer depois ponho o raciocinio aqui. From: Fernando Aires [EMAIL PROTECTED] Reply-To: obm-l@mat.puc-rio.br To: obm-l@mat.puc-rio.br Subject: Re: [obm-l] Moedas em sacos Date: Tue, 15 Feb 2005 13:05:28 -0200 Olá, Não sei se meu raciocínio está correto, mas eu pensei em resolver o problema da seguinte forma: Como sabemos que o saco é mais pesado, para a última medição (terceira), no pior caso, devemos ter 3 sacos. Mediríamos dois deles na balança, e se um for mais pesado, é este; se ambos forem iguais, o terceiro é o saco mais pesado. Dito isso, na segunda (penúltima) medição, devemos medir grupos de 3 sacos. Podemos medir 3 grupos, usando a mesma lógica da última medição. Portanto, deve chegar 9 sacos na segunda medição. Assim, na primeira medição, pelo mesmo raciocínio, teremos 3 grupos de 9 sacos. Portanto, o N máximo é 27. Espero que esteja certo... Beijos, -- -- Fernando Aires [EMAIL PROTECTED] Em tudo Amar e Servir -- On Sat, 12 Feb 2005 10:57:42 -0200, Rogerio Ponce [EMAIL PROTECTED] wrote: Ola' pessoal, Existem N sacos abertos com 10 moedas cada um. Um deles, defeituoso, tem 10 moedas iguais entre si, porem mais pesadas que o padrao. Os outros sacos tem as 10 moedas com o peso padrao (a principio desconhecido). Voce dispoe de uma balanca de 2 pratos, que fornece a diferenca de peso entre os pratos (prato da esquerda menos prato da direita). Qual o maior N que ainda permite a determinacao do saco defeituoso com apenas 3 leituras ? []'s Rogerio Ponce = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Moedas em sacos
Ola' Fernando, N=27 ainda e' pouco. Repare que vc esta' apenas usando a informacao de um dos pratos pesar mais que o outro, sem considerar o valor dessa diferenca, fornecido pela balanca. O fato e' que N pode ser mais alto que 27. []'s Rogerio Ponce From: Fernando Aires Olá, Não sei se meu raciocínio está correto, mas eu pensei em resolver o problema da seguinte forma: Como sabemos que o saco é mais pesado, para a última medição (terceira), no pior caso, devemos ter 3 sacos. Mediríamos dois deles na balança, e se um for mais pesado, é este; se ambos forem iguais, o terceiro é o saco mais pesado. Dito isso, na segunda (penúltima) medição, devemos medir grupos de 3 sacos. Podemos medir 3 grupos, usando a mesma lógica da última medição. Portanto, deve chegar 9 sacos na segunda medição. Assim, na primeira medição, pelo mesmo raciocínio, teremos 3 grupos de 9 sacos. Portanto, o N máximo é 27. Espero que esteja certo... On Sat, 12 Feb 2005 10:57:42 -0200, Rogerio Ponce wrote: Ola' pessoal, Existem N sacos abertos com 10 moedas cada um. Um deles, defeituoso, tem 10 moedas iguais entre si, porem mais pesadas que o padrao. Os outros sacos tem as 10 moedas com o peso padrao (a principio desconhecido). Voce dispoe de uma balanca de 2 pratos, que fornece a diferenca de peso entre os pratos (prato da esquerda menos prato da direita). Qual o maior N que ainda permite a determinacao do saco defeituoso com apenas 3 leituras ? []'s Rogerio Ponce _ 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] Moedas em sacos
Exatamente. E 126 tb e muito pouco...agora to achando que o maximo e 171. Daqui a pouco mudo de ideia denovo From: Rogerio Ponce [EMAIL PROTECTED] Reply-To: obm-l@mat.puc-rio.br To: obm-l@mat.puc-rio.br Subject: Re: [obm-l] Moedas em sacos Date: Tue, 15 Feb 2005 13:06:26 -0300 Ola' Fernando, N=27 ainda e' pouco. Repare que vc esta' apenas usando a informacao de um dos pratos pesar mais que o outro, sem considerar o valor dessa diferenca, fornecido pela balanca. O fato e' que N pode ser mais alto que 27. []'s Rogerio Ponce From: Fernando Aires Olá, Não sei se meu raciocínio está correto, mas eu pensei em resolver o problema da seguinte forma: Como sabemos que o saco é mais pesado, para a última medição (terceira), no pior caso, devemos ter 3 sacos. Mediríamos dois deles na balança, e se um for mais pesado, é este; se ambos forem iguais, o terceiro é o saco mais pesado. Dito isso, na segunda (penúltima) medição, devemos medir grupos de 3 sacos. Podemos medir 3 grupos, usando a mesma lógica da última medição. Portanto, deve chegar 9 sacos na segunda medição. Assim, na primeira medição, pelo mesmo raciocínio, teremos 3 grupos de 9 sacos. Portanto, o N máximo é 27. Espero que esteja certo... On Sat, 12 Feb 2005 10:57:42 -0200, Rogerio Ponce wrote: Ola' pessoal, Existem N sacos abertos com 10 moedas cada um. Um deles, defeituoso, tem 10 moedas iguais entre si, porem mais pesadas que o padrao. Os outros sacos tem as 10 moedas com o peso padrao (a principio desconhecido). Voce dispoe de uma balanca de 2 pratos, que fornece a diferenca de peso entre os pratos (prato da esquerda menos prato da direita). Qual o maior N que ainda permite a determinacao do saco defeituoso com apenas 3 leituras ? []'s Rogerio Ponce _ 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 = = 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] curvas
O que significa pendente de uma curva? Vi esse termo no Demidovich (se tiver certa a escrita)... Yahoo! Acesso Grátis - Internet rápida e grátis. Instale o discador do Yahoo! agora.
Re: [obm-l] Moedas em sacos
On Sat, 12 Feb 2005 10:57:42 -0200, Rogerio Ponce <[EMAIL PROTECTED]>wrote: Ola' pessoal, Existem N sacos abertos com 10 moedas cada um. Um deles, defeituoso, tem 10 moedas iguais entre si, porem mais pesadas que o padrao. Os outros sacos tem as 10 moedas com o peso padrao (a principio desconhecido). Voce dispoe de uma balanca de 2 pratos, que fornece a diferenca de peso entre os pratos (prato da esquerda menos prato da direita). Qual o maior N que ainda permite a determinacao do saco defeituoso com apenas 3 leituras ? []'s Rogerio Ponce Eu achei N = 242 mas não sei provar que este é o maior N possível. Suponhamos queuma moeda normal pese P e uma moeda mais pesada pese P+Q. PRIMEIRA PESAGEM: Colocamos121 sacos num prato e121 no outro. A balança indicará em que prato está o saco mais pesado e o também o valor de Q, igual a 1/10 da leitura da balança. SEGUNDA PESAGEM: Numeramos os 121 sacos que incluem o mais pesado de0 a 120 e fazemos o seguinte: Sacos0 a 10: 0 moedas no prato da E e 10 moedas no prato da D; Sacos 11 a 21: 1 moeda no prato da E e 9 moedas no prato da D; ... Sacos 11k a 11k+10: k moedas no prato da E e 10-k moedas no prato da D; ... Sacos 110 a 120: 10 moedas no prato da E e 0 moedas no prato da D. (obs: estou supondo que mesmo após colocar as moedas nos pratos da balança, continuamos a saber de que saco elas vieram. Por exemplo, podemos empilhar as moedas de um mesmo saco e operar a balança com cuidado de forma que as pilhas não desabem) Suponhamos que o número do saco mais pesado seja 11k + r (0 = r = 10). Nesse caso, os pesos em cada prato serão: E = 605P + kQ e D = 605P + (10-k)Q Logo, leitura da balança = E - D = (2k-10)Q. Como já sabemos o valor de Q, ficaremos sabendo o valor de k. Ou seja, após esta segunda pesagem, ficaremos sabendo que o saco mais pesado é um dos 11 seguintes: 11k, 11k+1, ..., 11k+10. TERCEIRA PESAGEM: Re-numeramos os 11 sacos que incluem o mais pesado de0 a 10 e fazemos o seguinte: Saco0: 0 moedas no prato da E e 10 moedas no prato da D; Saco 1: 1 moeda no prato da E e 9 moedas no prato da D; ... Saco m:m moedas no prato da E e 10-m moedas no prato da D; ... Saco 10: 10 moedas no prato da E e 0 moedas no prato da D. Suponhamos que o saco mais pesado seja o m-ésimo. Os pesos em cada prato serão: E = 55P + mQ e D = 55P + (10-m)Q. Leitura da balança = E - D = (2m-10)Q. Como conhecemos Q, podemos determinarm e acabou. []s, Claudio.
[obm-l] RE: [obm-l] [OFF] Livro: História da Matemática
Esse livro e bom ! Tem muita coisa interessante, principalmente no tempo dos gregos, Gauss, Newton, etc...Voce vai gostar. -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Bruno Soares Sent: Monday, February 14, 2005 9:00 PM To: obm-l@mat.puc-rio.br Subject: [obm-l] [OFF] Livro: História da Matemática Olá pessoal... Vou cursar essa matéria agora e gostaria de saber se alguém tem esse livro usado pra de vender: HISTÓRIA DA MATEMÁTICA Autor: CARL BENJAMIN BOYER Se alguem tiver entre em contato: [EMAIL PROTECTED] Atenciosamente; Bruno; = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] mais um de conjuntos
[P' U (P inter Q)] = [P' U P] inter [P' U Q] = (conjunto universo)inter [P'U Q] = [P' U Q] Não seria alternativa "d"? Errei algo? Yahoo! Acesso Grátis - Internet rápida e grátis. Instale o discador do Yahoo! agora.
Re: [obm-l] RE: [obm-l] [OFF] Livro: História da Matemática
Você encontra esse livro (e outro, como o do Eves) em praticamente qualquer cebo aqui no rio de janeiro..principal nos do centro da cidade.. Realmente é um livro muito interessante..embora eu prefira o do eves.. On Tue, 15 Feb 2005 10:08:55 -0800, Leandro Lacorte Recova [EMAIL PROTECTED] wrote: Esse livro e bom ! Tem muita coisa interessante, principalmente no tempo dos gregos, Gauss, Newton, etc...Voce vai gostar. -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Bruno Soares Sent: Monday, February 14, 2005 9:00 PM To: obm-l@mat.puc-rio.br Subject: [obm-l] [OFF] Livro: História da Matemática Olá pessoal... Vou cursar essa matéria agora e gostaria de saber se alguém tem esse livro usado pra de vender: HISTÓRIA DA MATEMÁTICA Autor: CARL BENJAMIN BOYER Se alguem tiver entre em contato: [EMAIL PROTECTED] Atenciosamente; Bruno; = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = -- A noção de infinito, de que é preciso se fazer um mistério em Matemática, resume-se no seguinte princípio: depois de cada número inteiro existe sempre um outro. (J. Tannery) = 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] Moedas em sacos
Caro Claudio, como sempre a sua engenhosidade é bem vinda. Mas N pode ser ainda maior... Grande abraço, Rogério. From: claudio.buffara Ola' pessoal, Existem N sacos abertos com 10 moedas cada um. Um deles, defeituoso, tem 10 moedas iguais entre si, porem mais pesadas que o padrao. Os outros sacos tem as 10 moedas com o peso padrao (a principio desconhecido). Voce dispoe de uma balanca de 2 pratos, que fornece a diferenca de peso entre os pratos (prato da esquerda menos prato da direita). Qual o maior N que ainda permite a determinacao do saco defeituoso com apenas 3 leituras ? []'s Rogerio Ponce Eu achei N = 242 mas não sei provar que este é o maior N possível. Suponhamos que uma moeda normal pese P e uma moeda mais pesada pese P+Q. PRIMEIRA PESAGEM: Colocamos 121 sacos num prato e 121 no outro. A balança indicará em que prato está o saco mais pesado e o também o valor de Q, igual a 1/10 da leitura da balança. SEGUNDA PESAGEM: Numeramos os 121 sacos que incluem o mais pesado de 0 a 120 e fazemos o seguinte: Sacos 0 a 10: 0 moedas no prato da E e 10 moedas no prato da D; Sacos 11 a 21: 1 moeda no prato da E e 9 moedas no prato da D; ... Sacos 11k a 11k+10: k moedas no prato da E e 10-k moedas no prato da D; ... Sacos 110 a 120: 10 moedas no prato da E e 0 moedas no prato da D. (obs: estou supondo que mesmo após colocar as moedas nos pratos da balança, continuamos a saber de que saco elas vieram. Por exemplo, podemos empilhar as moedas de um mesmo saco e operar a balança com cuidado de forma que as pilhas não desabem) Suponhamos que o número do saco mais pesado seja 11k + r (0 = r = 10). Nesse caso, os pesos em cada prato serão: E = 605P + kQ e D = 605P + (10-k)Q Logo, leitura da balança = E - D = (2k-10)Q. Como já sabemos o valor de Q, ficaremos sabendo o valor de k. Ou seja, após esta segunda pesagem, ficaremos sabendo que o saco mais pesado é um dos 11 seguintes: 11k, 11k+1, ..., 11k+10. TERCEIRA PESAGEM: Re-numeramos os 11 sacos que incluem o mais pesado de 0 a 10 e fazemos o seguinte: Saco 0: 0 moedas no prato da E e 10 moedas no prato da D; Saco 1: 1 moeda no prato da E e 9 moedas no prato da D; ... Saco m: m moedas no prato da E e 10-m moedas no prato da D; ... Saco 10: 10 moedas no prato da E e 0 moedas no prato da D. Suponhamos que o saco mais pesado seja o m-ésimo. Os pesos em cada prato serão: E = 55P + mQ e D = 55P + (10-m)Q. Leitura da balança = E - D = (2m-10)Q. Como conhecemos Q, podemos determinar m e acabou. []s, Claudio. _ Chegou o que faltava: MSN Acesso Grátis. Instale Já! http://www.msn.com.br/discador = 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] Teo de fermat provado com matematica elementar?
Por gentileza senhores, alguem poderia comentar sobre esta suposta prova usando apenas conceitos do ensino medio? http://xxx.lanl.gov/abs/math.GM/0502245 Um abraço Niski = 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] Propriedade de Elipse
Estou com um problema para demonstrar uma propriedade de elipse. Na realidade eu não tenho certeza absoluta que a propriedade é verdadeira, mas tudo me indica que sim. Eu tive um "flash" para resolver um exercício do IME que precisa dessa suposta propriedade hehe. Mas simplesmente não consigo encontrar um meio não analítico (geométrico) para demonstra-la. Agradeço qualquer ajuda, crítica ou comentário. Aqui está o endereço da imagem para a questão. http://bbonagura.blog.uol.com.br/images/elipse.jpg
Re: [obm-l] Teo de fermat provado com matematica elementar?
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Fabio Niski escreveu: | Por gentileza senhores, alguem poderia comentar sobre esta suposta prova | usando apenas conceitos do ensino medio? | | http://xxx.lanl.gov/abs/math.GM/0502245 | [...] Eu acho que a afirmação imediatamente após a equação 35 é um erro fatal, já que n não precisa ser par. (Apesar de que não há nenhum problema imediatamente, ele explora o fato de que a raiz (n/2)-ésima de (1/X + 2X + 2) é inteiro somente se (1/X + 2X + 2) é inteiro, o que se torna falso no caso n ímpar.) []s, - -- Fábio Dias Moreira -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.0 (MingW32) Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org iD8DBQFCEmmGp7qMXa2oQtsRAtKyAJ0eDAThajOsD8c4IEixJY6+9dAx4ACfex9s Og/Sxf5reOWucZCHehNpTSM= =O0ri -END PGP SIGNATURE- = 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] Moedas em sacos
Claudio, inspirado no seu raciocínio consegui chegar a 883. (Desculpe o plágio, mas gostei da sua idéia) Suponhamos que uma moeda normal pese P e uma moeda mais pesada pese P+Q. 1a pesagem: Colocamos 441 sacos num prato e 441 no outro. Se ficarem iguais obviamente será o outro saco, mas como isso é quase impossivel, a balança indicará em que prato está o saco mais pesado e o também o valor de Q, igual a 1/10 da leitura da balança. 2a pesagem: Numeramos os 441 sacos de 0 a 440 e fazemos o seguinte: Sacos de 0 a 20 --- nao pesamos. Sacos de 21 a 41 --- uma moeda na esquerda Sacos de 42 a 62 --- duas moedas na esquerda ... Sacos de 21k a 21k+20 --- k moedas na esquerda ... Sacos de 210 a 230 --- 10 moedas na esquerda Repetindo o processo com os outros sacos, para o lado direito da balança, chegamos finalmente ate o saco 440. Pesando, já conhecido o valor de Q, chegamos a um grupo final de 21 sacos, dentre os quais estará o mais pesado. Terceira pesagem: Renumerando os sacos de 0 a 20, faremos o seguinte: Não pesaremos o saco 0. Colocaremos K moedas do saco K na esquerda (caso 0K11) e colocaremos K moedas do saco K + 10 na direita (0K11) Assim, concluiremos qual o saco mais pesado. Por que acho (não tenho a menor certeza) que esse é o maior numero possivel: A ultima pesagem pode ter no máximo 21 sacos. A 1a pesagem deve ser usada para descobrirmos o valor de Q, fundamental para as proximas pesagens. Assim, a 2a pesagem deve reduzir de (N-1)/2 para 21. Como são 10 moedas em cada saco, podemos fazer 21 grupos, o que faz com que (N-1)/2max = 21^2 = 441 = N=883 ps.: tentando rapidamente generalizar o problema, caso existam X moedas em cada saco, Nmax = [(2X+1)^2]*2 + 1. Ou caso existam X moedas, e Y pesagens, Nmax = [(2X+1)^(Y-1)]*2+1 Ou ainda no remoto caso de haverem Z pratos (imaginem só, uma balança de prato com 3, 8, 20 pratos... ainda bem que isso é matematica, nao fisica) Nmax = [(ZX+1)^(Y-1)]*Z + 1. Acho q me empolguei, desculpem. On Tue, 15 Feb 2005 15:59:25 -0300, Rogerio Ponce [EMAIL PROTECTED] wrote: Caro Claudio, como sempre a sua engenhosidade é bem vinda. Mas N pode ser ainda maior... Grande abraço, Rogério. From: claudio.buffara Ola' pessoal, Existem N sacos abertos com 10 moedas cada um. Um deles, defeituoso, tem 10 moedas iguais entre si, porem mais pesadas que o padrao. Os outros sacos tem as 10 moedas com o peso padrao (a principio desconhecido). Voce dispoe de uma balanca de 2 pratos, que fornece a diferenca de peso entre os pratos (prato da esquerda menos prato da direita). Qual o maior N que ainda permite a determinacao do saco defeituoso com apenas 3 leituras ? []'s Rogerio Ponce Eu achei N = 242 mas não sei provar que este é o maior N possível. Suponhamos que uma moeda normal pese P e uma moeda mais pesada pese P+Q. PRIMEIRA PESAGEM: Colocamos 121 sacos num prato e 121 no outro. A balança indicará em que prato está o saco mais pesado e o também o valor de Q, igual a 1/10 da leitura da balança. SEGUNDA PESAGEM: Numeramos os 121 sacos que incluem o mais pesado de 0 a 120 e fazemos o seguinte: Sacos 0 a 10: 0 moedas no prato da E e 10 moedas no prato da D; Sacos 11 a 21: 1 moeda no prato da E e 9 moedas no prato da D; ... Sacos 11k a 11k+10: k moedas no prato da E e 10-k moedas no prato da D; ... Sacos 110 a 120: 10 moedas no prato da E e 0 moedas no prato da D. (obs: estou supondo que mesmo após colocar as moedas nos pratos da balança, continuamos a saber de que saco elas vieram. Por exemplo, podemos empilhar as moedas de um mesmo saco e operar a balança com cuidado de forma que as pilhas não desabem) Suponhamos que o número do saco mais pesado seja 11k + r (0 = r = 10). Nesse caso, os pesos em cada prato serão: E = 605P + kQ e D = 605P + (10-k)Q Logo, leitura da balança = E - D = (2k-10)Q. Como já sabemos o valor de Q, ficaremos sabendo o valor de k. Ou seja, após esta segunda pesagem, ficaremos sabendo que o saco mais pesado é um dos 11 seguintes: 11k, 11k+1, ..., 11k+10. TERCEIRA PESAGEM: Re-numeramos os 11 sacos que incluem o mais pesado de 0 a 10 e fazemos o seguinte: Saco 0: 0 moedas no prato da E e 10 moedas no prato da D; Saco 1: 1 moeda no prato da E e 9 moedas no prato da D; ... Saco m: m moedas no prato da E e 10-m moedas no prato da D; ... Saco 10: 10 moedas no prato da E e 0 moedas no prato da D. Suponhamos que o saco mais pesado seja o m-ésimo. Os pesos em cada prato serão: E = 55P + mQ e D = 55P + (10-m)Q. Leitura da balança = E - D = (2m-10)Q. Como conhecemos Q, podemos determinar m e acabou. []s, Claudio. _ Chegou o que faltava: MSN Acesso Grátis. Instale Já! http://www.msn.com.br/discador = Instruções para entrar na lista, sair da lista e usar a lista em
Re: [obm-l] Moedas em sacos
Legal, eu tinha limitado a ultima pesagem a 21 sacos fazendo Prato 1: 1 moeda do saco 1 2 moedas do saco 2 3 moedas do saco 3 ... 10 moeadas do saco 10 Prato 2: 1 moeda do saco 11 2 moedas do saco 12 3 moedas do saco 13 ... 10 moedas do saco 20 saco 21 ficando de fora da pesagem Certamente menos eficiente que seu metodo porem usava o fato que nao precisamos pesar todos os sacos. De cara ja da pra aumentar N de 242 pra 287 Faz exatamente oque vc fez e deixa 45 sacos de fora... se os pratos nao acusarem diferenca na primeira pesagem usamos meu metodo pouco eficiente de pesar 21 sacos de cada lado com 3 sobrando. Dai ou a terceira pesagem resolve entre os 21 sacos do prato mais pesado ou entre os 3 sacos que nunca foram pra balanca. Certamente usando o seu metodo mais eficiente vai dar pra deixar de fora bem mais que 45 na primeira pesagem, mas ainda nao fiz as contas. A questao e...como provar que o seu metodo e de fato o mais eficiente? From: claudio.buffara [EMAIL PROTECTED] Reply-To: obm-l@mat.puc-rio.br To: obm-l obm-l@mat.puc-rio.br Subject: Re: [obm-l] Moedas em sacos Date: Tue, 15 Feb 2005 14:57:21 -0300 On Sat, 12 Feb 2005 10:57:42 -0200, Rogerio Ponce wrote: Ola' pessoal, Existem N sacos abertos com 10 moedas cada um. Um deles, defeituoso, tem 10 moedas iguais entre si, porem mais pesadas que o padrao. Os outros sacos tem as 10 moedas com o peso padrao (a principio desconhecido). Voce dispoe de uma balanca de 2 pratos, que fornece a diferenca de peso entre os pratos (prato da esquerda menos prato da direita). Qual o maior N que ainda permite a determinacao do saco defeituoso com apenas 3 leituras ? []'s Rogerio Ponce Eu achei N = 242 mas não sei provar que este é o maior N possível. Suponhamos que uma moeda normal pese P e uma moeda mais pesada pese P+Q. PRIMEIRA PESAGEM: Colocamos 121 sacos num prato e 121 no outro. A balança indicará em que prato está o saco mais pesado e o também o valor de Q, igual a 1/10 da leitura da balança. SEGUNDA PESAGEM: Numeramos os 121 sacos que incluem o mais pesado de 0 a 120 e fazemos o seguinte: Sacos 0 a 10: 0 moedas no prato da E e 10 moedas no prato da D; Sacos 11 a 21: 1 moeda no prato da E e 9 moedas no prato da D; ... Sacos 11k a 11k+10: k moedas no prato da E e 10-k moedas no prato da D; ... Sacos 110 a 120: 10 moedas no prato da E e 0 moedas no prato da D. (obs: estou supondo que mesmo após colocar as moedas nos pratos da balança, continuamos a saber de que saco elas vieram. Por exemplo, podemos empilhar as moedas de um mesmo saco e operar a balança com cuidado de forma que as pilhas não desabem) Suponhamos que o número do saco mais pesado seja 11k + r (0 = r = 10). Nesse caso, os pesos em cada prato serão: E = 605P + kQ e D = 605P + (10-k)Q Logo, leitura da balança = E - D = (2k-10)Q. Como já sabemos o valor de Q, ficaremos sabendo o valor de k. Ou seja, após esta segunda pesagem, ficaremos sabendo que o saco mais pesado é um dos 11 seguintes: 11k, 11k+1, ..., 11k+10. TERCEIRA PESAGEM: Re-numeramos os 11 sacos que incluem o mais pesado de 0 a 10 e fazemos o seguinte: Saco 0: 0 moedas no prato da E e 10 moedas no prato da D; Saco 1: 1 moeda no prato da E e 9 moedas no prato da D; ... Saco m: m moedas no prato da E e 10-m moedas no prato da D; ... Saco 10: 10 moedas no prato da E e 0 moedas no prato da D. Suponhamos que o saco mais pesado seja o m-ésimo. Os pesos em cada prato serão: E = 55P + mQ e D = 55P + (10-m)Q. Leitura da balança = E - D = (2m-10)Q. Como conhecemos Q, podemos determinar m e acabou. []s, Claudio. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Moedas em sacos
Ok N=927 and counting... veja o meu reply pro email do Claudio From: Bruno Bruno [EMAIL PROTECTED] Reply-To: obm-l@mat.puc-rio.br To: obm-l@mat.puc-rio.br Subject: Re: [obm-l] Moedas em sacos Date: Tue, 15 Feb 2005 18:30:04 -0300 Claudio, inspirado no seu raciocínio consegui chegar a 883. (Desculpe o plágio, mas gostei da sua idéia) Suponhamos que uma moeda normal pese P e uma moeda mais pesada pese P+Q. 1a pesagem: Colocamos 441 sacos num prato e 441 no outro. Se ficarem iguais obviamente será o outro saco, mas como isso é quase impossivel, a balança indicará em que prato está o saco mais pesado e o também o valor de Q, igual a 1/10 da leitura da balança. 2a pesagem: Numeramos os 441 sacos de 0 a 440 e fazemos o seguinte: Sacos de 0 a 20 --- nao pesamos. Sacos de 21 a 41 --- uma moeda na esquerda Sacos de 42 a 62 --- duas moedas na esquerda ... Sacos de 21k a 21k+20 --- k moedas na esquerda ... Sacos de 210 a 230 --- 10 moedas na esquerda Repetindo o processo com os outros sacos, para o lado direito da balança, chegamos finalmente ate o saco 440. Pesando, já conhecido o valor de Q, chegamos a um grupo final de 21 sacos, dentre os quais estará o mais pesado. Terceira pesagem: Renumerando os sacos de 0 a 20, faremos o seguinte: Não pesaremos o saco 0. Colocaremos K moedas do saco K na esquerda (caso 0K11) e colocaremos K moedas do saco K + 10 na direita (0K11) Assim, concluiremos qual o saco mais pesado. Por que acho (não tenho a menor certeza) que esse é o maior numero possivel: A ultima pesagem pode ter no máximo 21 sacos. A 1a pesagem deve ser usada para descobrirmos o valor de Q, fundamental para as proximas pesagens. Assim, a 2a pesagem deve reduzir de (N-1)/2 para 21. Como são 10 moedas em cada saco, podemos fazer 21 grupos, o que faz com que (N-1)/2max = 21^2 = 441 = N=883 ps.: tentando rapidamente generalizar o problema, caso existam X moedas em cada saco, Nmax = [(2X+1)^2]*2 + 1. Ou caso existam X moedas, e Y pesagens, Nmax = [(2X+1)^(Y-1)]*2+1 Ou ainda no remoto caso de haverem Z pratos (imaginem só, uma balança de prato com 3, 8, 20 pratos... ainda bem que isso é matematica, nao fisica) Nmax = [(ZX+1)^(Y-1)]*Z + 1. Acho q me empolguei, desculpem. On Tue, 15 Feb 2005 15:59:25 -0300, Rogerio Ponce [EMAIL PROTECTED] wrote: Caro Claudio, como sempre a sua engenhosidade é bem vinda. Mas N pode ser ainda maior... Grande abraço, Rogério. From: claudio.buffara Ola' pessoal, Existem N sacos abertos com 10 moedas cada um. Um deles, defeituoso, tem 10 moedas iguais entre si, porem mais pesadas que o padrao. Os outros sacos tem as 10 moedas com o peso padrao (a principio desconhecido). Voce dispoe de uma balanca de 2 pratos, que fornece a diferenca de peso entre os pratos (prato da esquerda menos prato da direita). Qual o maior N que ainda permite a determinacao do saco defeituoso com apenas 3 leituras ? []'s Rogerio Ponce Eu achei N = 242 mas não sei provar que este é o maior N possível. Suponhamos que uma moeda normal pese P e uma moeda mais pesada pese P+Q. PRIMEIRA PESAGEM: Colocamos 121 sacos num prato e 121 no outro. A balança indicará em que prato está o saco mais pesado e o também o valor de Q, igual a 1/10 da leitura da balança. SEGUNDA PESAGEM: Numeramos os 121 sacos que incluem o mais pesado de 0 a 120 e fazemos o seguinte: Sacos 0 a 10: 0 moedas no prato da E e 10 moedas no prato da D; Sacos 11 a 21: 1 moeda no prato da E e 9 moedas no prato da D; ... Sacos 11k a 11k+10: k moedas no prato da E e 10-k moedas no prato da D; ... Sacos 110 a 120: 10 moedas no prato da E e 0 moedas no prato da D. (obs: estou supondo que mesmo após colocar as moedas nos pratos da balança, continuamos a saber de que saco elas vieram. Por exemplo, podemos empilhar as moedas de um mesmo saco e operar a balança com cuidado de forma que as pilhas não desabem) Suponhamos que o número do saco mais pesado seja 11k + r (0 = r = 10). Nesse caso, os pesos em cada prato serão: E = 605P + kQ e D = 605P + (10-k)Q Logo, leitura da balança = E - D = (2k-10)Q. Como já sabemos o valor de Q, ficaremos sabendo o valor de k. Ou seja, após esta segunda pesagem, ficaremos sabendo que o saco mais pesado é um dos 11 seguintes: 11k, 11k+1, ..., 11k+10. TERCEIRA PESAGEM: Re-numeramos os 11 sacos que incluem o mais pesado de 0 a 10 e fazemos o seguinte: Saco 0: 0 moedas no prato da E e 10 moedas no prato da D; Saco 1: 1 moeda no prato da E e 9 moedas no prato da D; ... Saco m: m moedas no prato da E e 10-m moedas no prato da D; ... Saco 10: 10 moedas no prato da E e 0 moedas no prato da D. Suponhamos que o saco mais pesado seja o m-ésimo. Os pesos em cada prato serão: E = 55P + mQ e D = 55P + (10-m)Q. Leitura da balança = E - D = (2m-10)Q. Como conhecemos Q, podemos determinar m e acabou. []s, Claudio. _ Chegou o que faltava: MSN Acesso
[obm-l] Problema
Quinze moedas de mesmo diâmetro são dispostas formando um triângulo eqüilátero. As faces de cada uma das moedas são pintadas ou de branco ou de preto. Prove que, qualquer que seja a pintura, existem três moedas de mesma cor cujos centros são vértices de um triângulo eqüilátero.-- Esta mensagem foi verificada pelo sistema de anti-virus e acredita-se estar livre de perigo.
Re: [obm-l] Moedas em sacos
Ola' Qwert, Bruno, Claudio e colegas da lista, o fato e' que N pode ser ainda maior que 927... []'s Rogerio. From: Qwert Smith Ok N=927 and counting... _ Chegou o que faltava: MSN Acesso Grátis. Instale Já! http://www.msn.com.br/discador = 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] Problema
benedito escreveu: Quinze moedas de mesmo diâmetro são dispostas formando um triângulo eqüilátero. As faces de cada uma das moedas são pintadas ou de branco ou de preto. Prove que, qualquer que seja a pintura, existem três moedas de mesma cor cujos centros são vértices de um triângulo eqüilátero. [...] Suponha que não há triângulo equilátero e considere o tabuleiro: . . . . a . . a a . . . . . . Os três quadrados marcados com a não podem ser da mesma cor. Suponha s.p.d.g. que eles são pintados da seguinte forma: . . . . O . . X X . . . 1 . . (Eu estou seguindo a convenção do Go -- O é branco, X é preto) O ponto 1 deve ser branco: . . . . O . 2 X X 2 . . O . . Os pontos 2 têm que ser pretos: . . . . O . X X X X . 3 O 3 . Os pontos 3 têm que ser brancos: . . . . * . X X X X . * O * . Mas então acabamos de formar um triângulo equilátero nos três pontos marcados. []s, -- Fábio Dias Moreira = 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] Moedas em sacos
Rogerio Ponce escreveu: Ola' Qwert, Bruno, Claudio e colegas da lista, o fato e' que N pode ser ainda maior que 927... [...] Considere todos os ternos (p, q, r) de inteiros com |p|, |q|, |r| = 10 e tais que mdc(p, q, r) = n (estou definindo mcd(x, 0) = |x|). Seja S o conjunto desses ternos. Eu afirmo que é possível fazer o pedido com N = #S. Para ver isso, faça uma bijeção entre os sacos e os ternos de S. Na i-ésima pesagem, coloque t_i moedas do saco associado a t no prato da direita (faça a coisa natural no caso t_i 0). Como t pertence a S = -t pertence a S, a balança acusa um valor de t_i*d, onde d é a diferença de peso entre as moedas defeituosas. Logo as três pesagens revelarão o valor de t*d. Como d 0 e as três componentes de t são primas entre si, o mdc real entre as três componentes de t é exatamente d, logo é possível achar t. Agora o problema é achar N. Pelo PIE, não é difícil ver que #S = 21^3 - #T_2 - #T_3 - #T_5 - #T_7 + #T_6 + #T_10 + 1 onde #T_n é o conjunto dos ternos com norma do sup = 10 e o mcd entre as componentes é um múltiplo de n. Então #T_2 = 11^3 #T_3 = 7^3 #T_5 = 5^3 #T_6 = #T_7 = #T_10 = 3^3 Logo N = #S_1 = 9261 - 1331 - 343 - 125 - 27 + 27 + 27 + 1 = 7490. Isso também prova que, se todas as pesagens forem balanceadas, essa *é* a cota superior, logo basta provar que pesagens não-balanceadas não permitem ir além de um limite inferior a 7490. (O meu raciocínio está certo? A contagem está certa; eu conferi com um programinha em Python.) []s, -- Fábio Dias Moreira = 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 =