Re: [obm-l] Moedas em sacos
Fábio Dias Moreira escreveu: 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. [...] 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. [...] Desculpem -- eu quero dizer 7491. O terno (0, 0, 0) pode ser adicionado a S sem risco de ser confundido com algum dos outros ternos. []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
Agora sim, e' 7491 mesmo ! Valeu Fabio, Fernando, Claudio, Bruno e Qwert ! []'s Rogerio Ponce. From: Fábio Dias Moreira Fábio Dias Moreira escreveu: 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. [...] 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. [...] Desculpem -- eu quero dizer 7491. O terno (0, 0, 0) pode ser adicionado a S sem risco de ser confundido com algum dos outros ternos. []s, -- Fábio Dias Moreira _ 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
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 =
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.
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 =
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 Grátis
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] 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 =
