-
- Quantas pesagens em uma balança de pratos são necessárias para encontrar uma moeda falsa entre oito moedas se a moeda falsa puder tanto ser mais pesada quanto mais leve do que as outras? Descreva um algoritmo para encontrar a moeda falsa usando este número de pesagens.
*9. Quantas pesagens em uma balança de pratos são necessárias para encontrar uma moeda falsa entre 12 moedas se a moeda falsa for mais leve do que as outras? Descreva um algoritmo para encontrar a moeda mais leve usando este número de pesagens.
- Quantas pesagens em uma balança de pratos são necessárias para encontrar uma moeda falsa entre oito moedas se a moeda falsa puder tanto ser mais pesada quanto mais leve do que as outras? Descreva um algoritmo para encontrar a moeda falsa usando este número de pesagens.
*9. Quantas pesagens em uma balança de pratos são necessárias para encontrar uma moeda falsa entre 12 moedas se a moeda falsa for mais leve do que as outras? Descreva um algoritmo para encontrar a moeda mais leve usando este número de pesagens.
Passo 1
O enunciado traz dois problemas de “moeda falsa” usando balança de pratos. No problema 8 temos
moedas e a falsa pode ser tanto mais pesada quanto mais leve. No problema 9 temos
moedas e sabemos que a falsa é mais leve. O conteúdo usado é análise de informação em cada pesagem (cada pesagem tem três resultados possíveis: esquerda desce, direita desce ou equilíbrio) e construção de algoritmos que dividem as moedas em grupos adequados.
Passo 2
Para o problema 8 precisamos distinguir
moedas e ainda saber se a falsa é mais leve ou mais pesada, totalizando
hipóteses. Em
pesagens obtemos
resultados distintos. Logo buscamos o menor
tal que
Testando,
e
. Portanto
.
Passo 3
Algoritmo em 3 pesagens para 8 moedas
:
1ª pesagem: pese
contra
.
- Se equilibrar, a falsa está em
.
2ª pesagem: pesecontra . - Se desequilibrar, a mais pesada ou a mais leve será a falsa e já sabemos o sentido.
- Se equilibrar (impossível nesse ramo), seria contradição.
- Se desbalancear (por exemplo, esquerda desceu), a falsa está em
e sabemos se ela é pesada ou leve comparando o sentido do desvio.
2ª pesagem: escolha três moedas do lado baixo e três do alto de forma simétrica, por exemplo pesevs . - Se equilibrar, a falsa é a não pesada das duas que restaram deste grupo de seis; faça a 3ª pesagem entre essas duas para identificá-la e seu tipo (leve/pesada).
- Se não equilibrar, resta um grupo de três no qual já sabemos se procuramos a mais pesada ou a mais leve.
3ª pesagem: pese duas dessas três; ou encontra logo a falsa ou, se equilibrar, sabemos que é a terceira.
Passo 4
Para o problema 9 temos
hipóteses (já que a falsa é sempre mais leve). Buscamos
tal que
Novamente
e
, logo
.
Passo 5
Algoritmo em 3 pesagens para 12 moedas
, falsa mais leve:
1ª pesagem: pese
vs
.
- Se equilibrar, a falsa está em
. - Se um lado subir, a falsa está nesse lado que subiu.
2ª pesagem (supondo que o grupo de 4 suspeitas seja
): pese 2 moedas de
contra 2 moedas conhecidas boas.
- Se equilibrar, a falsa fica entre as 2 não pesadas de
. - Se um lado subir, a falsa é a que está nesse lado que subiu.
3ª pesagem: compare as duas candidatas ou pese uma candidata contra uma moeda boa. Em qualquer caso identifica-se qual é a falsa.
Resposta
(8) São necessárias 3 pesagens.
(9) São necessárias 3 pesagens.
(9) São necessárias 3 pesagens.