OBM - Carlinhos pensa num número ímpar positivo menor do que 100. Pedrinho se dispõe a descobrir que número é esse fazendo a seguinte pergunta, quantas vezes forem necessárias: “O número que você pensou é maior, menor ou igual a x ?”. Note que x é um número que Pedrinho escolhe. Quantas perguntas desse tipo Pedrinho poderá ter que fazer até descobrir o número pensado por Carlinhos?
a) 5
b) 7
c) 15
d) 25

Passo 1

O enunciado diz que Carlinhos pensa num número ímpar positivo menor que 100, ou seja, num dos 50 valores
1,3,5,dots,99
Pedrinho pergunta repetidamente “o número que você pensou é maior, menor ou igual a x?”. Cada pergunta tem três respostas possíveis: “maior”, “menor” ou “igual”. Em termos de teoria, isso é uma busca binária (já que “igual” encerra o jogo e “maior”/“menor” dividem o conjunto restante ao meio).

Passo 2

Inicialmente há 50 candidatos. Se em uma pergunta com valor de corte x Carlinhos responder “maior” ou “menor”, o conjunto de candidatos cai para, no máximo, cerca de metade dos casos, isto é, para no máximo
llceil 50-12rrceil = 25
(“ -1” porque excluímos o próprio x do conjunto quando a resposta não é “igual”.)

Passo 3

Em geral, se restam N candidatos e o pivô está bem escolhido no meio, uma resposta “maior” ou “menor” deixa no pior caso
llceilN-12rrceil
candidatos. Para chegar a apenas 1 candidato precisamos de k perguntas de modo que
2^k >= 50
Como 2^5=32<50 e 2^6=64>=50, isso mostra que são necessárias pelo menos 6 perguntas nesse processo de divisão ao meio.

Passo 4

Por fim, mesmo quando sobra um único candidato, precisamos de uma pergunta final do tipo “é igual a este número?” para confirmar “igual” e encerrar a busca. Assim, o total no pior caso fica
6 (divisões) + 1 (confirmação) = 7 õçã

Resposta

(b) 7

Exercícios de Livros Relacionados