Flashcard FC242074
Qual é o critério informacional para determinar o número mínimo de pesagens numa balança de pratos para identificar uma peça mais pesada entre N peças?
Problemas Envolvendo Balança de Pratos
CESGRANRIO · 2010
Qual é o critério informacional para determinar o número mínimo de pesagens numa balança de pratos para identificar uma peça mais pesada entre N peças?
Mostrar resposta e comentário
Resposta
O mínimo w é o menor inteiro tal que \(3^w \ge N\).Explicação e exemplo:
Cada pesagem tem 3 resultados (esquerda mais pesada, direita mais pesada ou equilíbrio), logo com w pesagens distinguimos até \(3^w\) possibilidades. Assim escolhemos o menor w com \(3^w\ge N\).
Exemplo (N = 13):
Calcule \(3^2=9<13\) e \(3^3=27\ge13\), logo são necessárias 3 pesagens.
Estratégia construtiva (garantidora):
1) Pese 4 vs 4, deixando 5 de fora.
- Se empatar → a pesada está entre as 5: pese 2 vs 2 (deixando 1 de fora).
- Se empatar → a de fora é a pesada.
- Se não empatar → pese 1 vs 1 do par mais pesado para achar a pesada.
- Se não empatar → o grupo de 4 do lado mais pesado contém a distinta: pese 1 vs 1 nesse grupo (deixando 2 de fora).
- Se empatar → a pesada está nas 2 deixadas; pese 1 vs 1 para identificar.
- Se não empatar → o vencedor é a pesada.
Em todos os ramos, no pior caso usam-se 3 pesagens.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/236890
Conteúdo do catálogo FC Concursos · Atualizado em