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
moedas, sendo
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
moedas falsas.
Passo 2
O total de configurações possíveis de quais são as
moedas falsas é dado por
Passo 3
Cada pesagem na balança produz
resultados distintos. Em
pesagens adaptativas podemos diferenciar no máximo
configurações, pois cada sequência de resultados de
pesagens é uma das
“palavras” em um alfabeto de tamanho 3.
Passo 4
Para que seja possível distinguir todas as
configurações devemos ter
Como
segue que
Resposta
Pelo menos
pesagens são necessárias.