aforismos e afins

29 janeiro 2006

Quizz 6

Existe uma balança com dois pratos onde pretende conseguir pesar qualquer quantidade unitária de 1 a 40. Ou seja, qualquer número inteiro positivo entre 1 e 40, inclusivé, isto é: 1, 2, 3, 4, ... 38, 39, 40. Tem à sua disposição todos os pesos unitários de 1 a 40.

1. Qual o número mínimo de pesos que lhe permite fazer todas as pesagens unitárias de 1 a 40? Quais são os pesos escolhidos? Explique como chegou à sua resposta.

2. Qual o número mínimo de pesos que lhe permite fazer todas as pesagens unitárias de 1 a n? Ou seja, qual a regra geral a usar? Explique a intuição para esse resultado.

3. Demonstre o resultado obtido na resposta anterior.

-------------------------------------------------------------

P A R A B É N S ao Luís Pedro que respondeu correctamente às três perguntas, para além de me ter enviado uma demonstração inatacável em pdf que provavelmente "dissolverei" com a minha para depois propor uma versão relativamente friendly aqui no blogue. O entusiasmo do Luís é um incentivo a todos: depois de perceberem bem "o que se passa" na resposta à pergunta inicial, ficarão viciados para conseguir chegar à fórmula geral. E, depois de descoberta esta, não dormirão descansados enquanto não conseguirem demonstrar o resultado. [Luís, satisfaz lá a minha curiosidade: tens mais 'pica' a resolver estas coisas inúteis ou a escrever sobre o Hayek / Negri?]

PARABÉNS ao Miguel Madeira que, se eu bem li a sua demonstração, só lhe falta um minúsculo passo para ter a terceira resposta totalmente correcta. Aliás, aquilo que me parece faltar é algo que tu apontaste numa resposta anterior à laia de nota de rodapé. Envia-me um mail se quiseres trocar uma ideias sobre o assunto.

Parabéns ao jcd, ao Miguel André e ao Karloos que responderam correctamente às duas primeiras perguntas.

-------------------------------------------------------------

Como o blogue hoje em dia anda (alegremente) a passo de caracol, ainda há muito tempo até à publicação das respostas, que de resto tenciono publicar por partes. Obrigado a todos pela participação.

-------------------------------------------------------------

Pista: para quem nunca foi à praça antes do advento das balanças eletrónicas (como parece ser o caso do Bruno Gonçalves), uma balança com dois pratos tem mesmo dois pratos (utilizáveis) e não apenas um. Como o símbolo da Justiça, estão a ver? E mais não digo.

--------------------------------------------------------------

Os quizzs anteriores podem ser encontrados nos links seguintes. Enunciados: quizz 1, quizz 1 reescrito, quizz 2, quizz 3, quizz 4, quizz 5. Respostas: quizz 1, quizz 2, quizz 3, quizzs 4 e 5.

posted by Tiago Mendes at 9:17 da manhã

12 Comments:

  • Empiricamente, cheguei lá com 4 pesos, 1, 3, 9 e 27.

    O primeiro peso é o 1.
    O segundo peso terá que permitir fazer o 2 por subtração, logo terá que ser o 3. Assim, já temos todos os números de 1 a 4.

    O terceiro peso terá que conseguir fazer o 5 por subtração. 9-4=5.

    Com o 9 dá para pesar tudo até 13.

    O quarto peso terá que fazer 14 por subtração. 27-13=14.

    No outro limite, 27+13=40

    Um abraço
    jcd

    By Blogger jcd, at 2:11 da tarde  

  • Não deverias estar a trabalhar, seu malandro? (ai, tanta tusa)

    By Anonymous Anónimo, at 6:32 da tarde  

  • Máximo a pesar com 'n' pesos é o somatório desde i=0 até n de 3^i.

    Para demosntrações matemáticas é que já não estou aqui, a ferrugem já não me deixa entrar em formalismos.

    By Blogger jcd, at 10:23 da manhã  

  • Começando com peso 1, e acrescentando o peso 3, já conseguimos pesar tudo até 4, porque o 2 pode ser conseguido, pondo o 3 num prato e a coisa no outro, mais o peso 1! Se se acrescentar o peso 9, já pesamos tudo até 13, e se acrescentarmos o peso 27, já conseguimos pesa tudo até 40, só com 4 pesos. Seguindo este raciocinio, temos que multiplicar sempre o peso anterior por 3, para optimizar! Logo, o peso máximo que conseguimos pesar com x pesos, é igual á soma de todos os pesos, que é também igual à soma geométrica de razão 3, para x termos, contando a partir de 0 a x. Exemplo: com os pesos, 1, 3, 9, 27, e 81, conseguimos pesar até 121, que é igual á soma da série geométrica de razão 3 == (1-3^(m+1))/(1-3), quando o numero de pesos é m+1.
    Se queremos pesar qualquer coisa com peso n, a soma geométrica tem que ser maior ou igual a n, ou seja: (1-3^(m+1))/(1-3)>=n, ou fazendo contas o numero de pesos (m+1) vai ter que ser maior ou igual que: m+1>=log(n)/log3
    Miguel André

    By Anonymous Anónimo, at 12:27 da tarde  

  • Esqueci-me da 3. É só substituir 40 na formula que enviei! m+1>=log(n)/log(3)
    m+1=log40/log3
    m=1>=1.602/0.4771
    m+1>=3.3577, logo o número de pesos é 4!

    By Anonymous Anónimo, at 3:34 da tarde  

  • Eu estava-me a admirar de não ser um dos contemplados com os parabéns. Ainda mais me admirava pelo facto de este parecer tão fácil à primeira. Claro está, deixei-me levar...
    Em relação à primeira questão apenas os pesos 1, 3, 9, 27 são necessários.
    Em relação à segunda onde se lê 2 na minha primeira resposta deve ler-se 3.
    Penso que desta vez estará correcto. Se se confirmar tentarei fazer a demosntração como forma de penitência por ter errado à primeira :)

    By Blogger Carlos Guimarães Pinto, at 10:17 da tarde  

  • Era capaz de jurar que enviei duas respostas erradas antes. Deve ter sido o subconsciente que me impediu de as publicar. Seja como for, aqui vai a resposta à segunda questão:
    para qualquer valor n, o menor número k de pesos necessáros será o maior valor de k possível em que 3^(k-1) < n.
    Como não enviei nenhuma resposta errada antes, deixei de sentir o dever de me penitenciar com a demonstração... De qualquer, se tiver um tempinho tentarei :)

    By Blogger Carlos Guimarães Pinto, at 11:45 da tarde  

  • «depois de perceberem bem "o que se passa" na resposta à pergunta inicial, ficarão viciados para conseguir chegar à fórmula geral. E, depois de descoberta esta, não dormirão descansados enquanto não conseguirem demonstrar o resultado» lol! lol! agora fizeste-me rebolar a rir! bravo tiago, bravo! vai ficar conhecido como o dealer dos quizz! ;)

    By Blogger aL, at 9:14 da tarde  

  • Se eu tiver só o peso 1 consigo (obviamente), pesar algo que pese 1.

    Se eu tiver os pesos 1 e 3, consigo pesar de 1 a 4: para o 1, ponho o peso 1; para o 2, ponho o peso 3 num prato e o 1 no outro prato (e ponho o que quero pesar nesse).

    Com os pesos 1,3 e 9, consigo pesar de 1 a 13: para pesar de 1 a 4, esqueço o 9, e uso só o 1 e o 3 (como atrás); para pesos de 10 a 13, ponho o 9 e mais uma combinação com o 1 e o 3 (9 somado com qualquer coisa entre 1 e 4 dá qualquer coisa entre 10 e 13); para pesos entre 5 e 8, ponho o 9 e também uma combinação do 1 e o 3, mas com os pratos trocados (ou seja, a subtrair e não a adicionar) – 9 menos qualquer coisa entre 1 e 4 dá qualquer coisa entre 8 e 5.

    Sub-questão 1:

    Se eu adicionar o peso 27, consigo pesar até 40: para pesos até 13, uso só os pesos {1,3,9}; para pesos entre 14 e 26, uso o 27 e subtraiu (pondo nos pratos opostos) o resultado de uma combinação de {1,3,9}; para valores entre 28 e 40, adiciono uma combinação de {1,3,9} (que, recorde-se, corresponde aos pesos de 1 a 13) ao peso 27.

    Resposta: preciso dos pesos 1,3,9 e 27

    By Blogger Miguel Madeira, at 10:38 da tarde  

  • resposta 2:

    Já cheguei à conclusão que isto segue as potências de 3 (1, 3, 9, 27…), o que faz sentido, já que cada peso pode assumir 3 estados (no prato direito, no prato esquerdo e na mesa).

    Assim, se eu tiver “x” pesos, o valor máximo que posso pesar é 3^0 + 3^1+…+ 3^(x-1) = (1-3^x)/(1-3) = (3^x – 1)/2

    Como o que eu quero é o contrário (quantos pesos preciso para pesar até “n”), temos que

    n = (3^x – 1)/2 ? 3^x = 2*n + 1 ? x = ln (2*n + 1)/ln (3) [arredondado para cima]

    By Blogger Miguel Madeira, at 11:16 da tarde  

  • pergunta 3:

    Em vez de tentar demonstrar a fórmula que diz “Qual o número mínimo de pesos que lhe permite fazer todas as pesagens unitárias de 1 a n”, vou tentar fazer ao contrário: demonstrar a formula que diz “qual o número máximo de pesagens unitárias de 1 a n que consigo fazer com “x” pesos". Creio que demonstrando uma, demonstro a outra.

    Assim, a fórmula era:

    n = (3^x – 1)/2

    Vou tentar demonstrar isso utilizando a “indução matemática”.

    Para x = 1, não há dúvida que a fórmula está correcta: com 1 peso, a maior sequência de 1 a n que se consegue é… 1 = (3^1 – 1)/2

    Agora, admitindo que a fórmula está correcta para “x-1”, estará correcta para “x”?

    Se estiver correcta para “x-1”, isso que dizer que com “x-1” pesos, conseguimos fazer pesagens até [3^(x-1) – 1]/2 unidades. Para simplificar, vamos chamar isso de “m”

    Se juntarmos um peso adicional, conseguiremos fazer pesagens até quanto? Se o peso for de 2m+1, conseguimos fazer pesagens até 3m+1 (para fazer pesagens entre 2m+2 e 3m+1, é somar ao peso “2m+1” uma das combinações de pesos entre [1,m]; para pesos entre m+1 e 2m, é subtrair, pondo ao contrário na balança).

    Se o peso adicionado for menor que 2m+1, o valor máximo será menor que 3m+1; se for maior que 2m+1, não se atinge as pesagens logo a seguir a “m” (p.ex., se for 2m+2, é impossível atingir o peso “m+1”).

    Assim, o peso que se deve adicionar é o “2m+1”, logo, o máximo de pesagens que se consegue é 3m+1

    Ora, se “m” for [3^(x-1) – 1]/2, então 3m+1 = [3*3^(x-1) – 3]/2 + 1 = (3^x – 3)/2 + 2/2 = (3^x – 3 + 2)/2 = (3^x – 1)/2

    Ou seja, se a fórmula for válida para “x-1”, é valida para “x”. Como é válida para x=1, então é sempre válida.

    Portanto, se a fórmula n = (3^x – 1)/2 é válida, também o é a formula x = ln (2*n + 1)/ln (3)

    By Blogger Miguel Madeira, at 1:02 da manhã  

  • O que faltará na terceira resposta é referir que o numero de pesos tem que ser arredondado para cima?

    By Blogger Miguel Madeira, at 6:20 da tarde  

Enviar um comentário

<< Home