Paulo propôs a Rodrigo um jogo, no qual Paulo escolhe um número entre 1 e 32 que Rodrigo deve tentar adivinhar. A cada palpite de Rodrigo, Paulo dá uma pista, dizendo se o palpite

Gabarito

B

Comentário do professor

A chave é modelar o processo por uma árvore de decisões: a cada palpite há três respostas possíveis, mas se der "é igual" o jogo termina; caso contrário restam as duas ramificações "maior" ou "menor".

Seja M(k) o máximo de números distinguíveis em até k palpites. Ao fazer o primeiro palpite, um número pode ser acertado de imediato (1) e, se não, cada ramo ("maior"/"menor") permite resolver até M(k−1) números com os k−1 palpites restantes. Assim surge a recorrência M(k)=1+2·M(k−1), com M(1)=1.

Da recorrência obtém-se a soma geométrica \(M(k)=1+2+4+\dots+2^{\,k-1}=2^{k}-1\).

Queremos \(2^{k}-1\ge 32\). Como \(2^{5}-1=31<32\) e \(2^{6}-1=63\ge32\), o menor k que atende é k=6.

Logo, o número máximo de palpites necessários é 6 palpites.