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
?”. Note que
é 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
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
Pedrinho pergunta repetidamente “o número que você pensou é maior, menor ou igual a
?”. 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á
candidatos. Se em uma pergunta com valor de corte
Carlinhos responder “maior” ou “menor”, o conjunto de candidatos cai para, no máximo, cerca de metade dos casos, isto é, para no máximo
(“
” porque excluímos o próprio
do conjunto quando a resposta não é “igual”.)
Passo 3
Em geral, se restam
candidatos e o pivô está bem escolhido no meio, uma resposta “maior” ou “menor” deixa no pior caso
candidatos. Para chegar a apenas 1 candidato precisamos de
perguntas de modo que
Como
e
, 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
Resposta
(b) 7