3.Em uma coleção de 10 moedas, 4 moedas são falsificadas e pesam menos do que as moedas verdadeiras.Considere uma balança de dois pratos e encontre uma boa cota inferior no número de pesagens para identificar todas as moedas falsificadas. (Suponha que a balança tem três estados:inclinada para a esquerda,inclinada para a direita ou equilibrada.)

Passo 1

O enunciado diz que temos 10 moedas, sendo 4 delas falsificadas (mais leves), e dispomos de uma balança de dois pratos que pode inclinar para a esquerda, para a direita ou equilibrar. Queremos uma cota inferior para o número de pesagens necessárias para identificar todas as 4 moedas falsas.

Passo 2

O total de configurações possíveis de quais são as 4 moedas falsas é dado por
binom104 ;=; 210

Passo 3

Cada pesagem na balança produz 3 resultados distintos. Em m pesagens adaptativas podemos diferenciar no máximo
3^m
configurações, pois cada sequência de resultados de m pesagens é uma das 3^m “palavras” em um alfabeto de tamanho 3.

Passo 4

Para que seja possível distinguir todas as 210 configurações devemos ter
3^m ;>=; 210
Como
3^4 = 81 < 210 e 3^5 = 243 >= 210,
segue que
m ;>=; 5

Resposta

Pelo menos 5 pesagens são necessárias.

Exercícios de Livros Relacionados