*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.
*10. Uma de quatro moedas pode ser falsa. Se ela for falsa, pode ser mais leve ou mais pesada do que as outras. Quantas pesagens são necessárias, usando uma balança de pratos, para determinar se existe uma moeda falsa e, se existir, se ela é mais leve ou mais pesada do que as outras? Descreva um algoritmo para encontrar a moeda falsa e determinar se ela é mais leve ou mais pesada do que as outras usando este número de pesagens.
*10. Uma de quatro moedas pode ser falsa. Se ela for falsa, pode ser mais leve ou mais pesada do que as outras. Quantas pesagens são necessárias, usando uma balança de pratos, para determinar se existe uma moeda falsa e, se existir, se ela é mais leve ou mais pesada do que as outras? Descreva um algoritmo para encontrar a moeda falsa e determinar se ela é mais leve ou mais pesada do que as outras usando este número de pesagens.
Passo 1
O enunciado pede: temos doze moedas idênticas, exatamente uma é falsa e é mais leve do que as outras. Usando balança de pratos, queremos o número mínimo de pesagens para localizar a falsa e um algoritmo que opere nesse número de passos. Conteúdo: conhecimento de informação ternária por pesagens.
Passo 2
Cada pesagem tem três resultados possíveis (prato esquerdo mais leve, prato direito mais leve ou equilíbrio). Com
pesagens podemos distinguir até
situações. Precisamos encontrar uma falsa entre doze moedas, logo
Como
, o número mínimo de pesagens é
.
Passo 3
Algoritmo em até três pesagens:
Primeiro, divida as doze moedas em três grupos ,
e
de quatro moedas cada.
Na primeira pesagem, compare contra
. Se equilibrar, a falsa está em
; caso contrário, a falsa pertence ao grupo que ficou mais leve. Denomine esse grupo de
.
Agora sobram quatro moedas suspeitas em e duas pesagens disponíveis. Na segunda pesagem, selecione duas delas (chame-as de 1 e 2) e compare 1 vs 2. Se 1 e 2 se equilibrarem, a falsa está entre as duas restantes (3 e 4) e basta usar a terceira pesagem para compará-las: a mais leve é a falsa. Se 1 ficar mais leve que 2, então a moeda 1 é a falsa e não é preciso usar a terceira pesagem.
Primeiro, divida as doze moedas em três grupos
Na primeira pesagem, compare
Agora sobram quatro moedas suspeitas em
Passo 4
O enunciado pede: temos quatro moedas, pode haver no máximo uma falsa que pode ser mais leve ou mais pesada do que as outras. Usando balança de pratos, queremos o número mínimo de pesagens para determinar se existe falsa, qual é ela e se é leve ou pesada. Conteúdo: análise de informação ternária com estado binário de defeito.
Passo 5
Cada pesagem dá três resultados e precisamos distinguir até
casos possíveis (quatro moedas
leve/pesada mais o caso “nenhuma falsa”). Logo
Como
, o número mínimo de pesagens é
.
Passo 6
Algoritmo em até duas pesagens:
Na primeira pesagem, compare moeda 1 contra moeda 2. Se equilibrar, então moedas 1 e 2 são genuínas e a suspeita está em {3,4}. Na segunda pesagem, compare moeda 3 contra moeda 4. Se equilibrar, não há moeda falsa. Se não equilibrar, a que ficar mais leve ou mais pesada (conforme o prato) é a falsa e seu tipo é dado por esse desvio.
Se na primeira pesagem 1 e 2 não equilibrarem, então a falsa é ou 1 ou 2, e moedas 3 e 4 são genuínas. Suponha que 1 ficou mais leve que 2; isso indica que ou 1 é falsa e leve, ou 2 é falsa e pesada. Para resolver, na segunda pesagem compare 1 contra 3. Se equilibrar, a falsa é a moeda 2 e ela é pesada (pois na primeira pesagem o prato com 2 ficou para baixo). Se não equilibrar, a moeda que descai mais leve ou mais pesada confirma a hipótese sobre a 1 (ela será mais leve neste caso).
Na primeira pesagem, compare moeda 1 contra moeda 2. Se equilibrar, então moedas 1 e 2 são genuínas e a suspeita está em {3,4}. Na segunda pesagem, compare moeda 3 contra moeda 4. Se equilibrar, não há moeda falsa. Se não equilibrar, a que ficar mais leve ou mais pesada (conforme o prato) é a falsa e seu tipo é dado por esse desvio.
Se na primeira pesagem 1 e 2 não equilibrarem, então a falsa é ou 1 ou 2, e moedas 3 e 4 são genuínas. Suponha que 1 ficou mais leve que 2; isso indica que ou 1 é falsa e leve, ou 2 é falsa e pesada. Para resolver, na segunda pesagem compare 1 contra 3. Se equilibrar, a falsa é a moeda 2 e ela é pesada (pois na primeira pesagem o prato com 2 ficou para baixo). Se não equilibrar, a moeda que descai mais leve ou mais pesada confirma a hipótese sobre a 1 (ela será mais leve neste caso).
Resposta
Duas pesagens são suficientes e necessárias.