Re: ajuda

["Bruno F. C. Leite" <bruleite@xxxxxxxxxx>]

Explicando melhor:

A pessoa A pensa num número de 0 a 15. A pessoa B tem que adivinhar o número
que A pensou fazendo perguntas cuja resposta seja "sim" ou "não", por
exemplo: "o número é maior que 4?", etc.

a)Mostre que com no máximo 4 perguntas, B consegue acertar o número.

b)Se A puder mentir uma vez no máximo (ele pode mentir se quiser, não é
obrigado), quantas perguntas são necessárias?

Acho que agora está certinho.

Bruno
-----Mensagem original-----
De: Bruno F. C. Leite <bruleite@uol.com.br>
Para: obm-l@mat.puc-rio.br <obm-l@mat.puc-rio.br>
Data: Quarta-feira, 18 de Abril de 2001 22:42
Assunto: Re: ajuda


>Estou me lembrando de um problema muito legal: uma pessoa escolhe um número
>de 0 a 15, a outra pessoa tem que descobrir que número é, fazendo perguntas
>com resposta "sim" ou "não". O detalhe é que o cara que pensou no número
>pode mentir 1 vez se quiser. Qual é o número mínimo de perguntas que são
>suficientes para descobrir o numero pensado?
>
>Bruno
>
>
>-----Mensagem original-----
>De: Alek <ksander@ig.com.br>
>Para: obm-l@mat.puc-rio.br <obm-l@mat.puc-rio.br>
>Data: Domingo, 15 de Abril de 2001 08:05
>Assunto: Re: ajuda
>
>
>>Eu responderia que o menor numero de perguntas é sete.
>>
>>Como cheguei a este numero?
>>A primeira coisa foi lembrar de uma aula de digital onde estava aprendendo
>>umas das formas de um circuito quantizar um valor, ou seja, passa-lo para
>>binario, e este era o metodo que gastava menos instruçoes, era mais ou
>>menos assim.
>>
>>Pergunta se o numero é menor que o numero mediano do universo em que se
>>esta trabalhando no momento
>>
>>No caso sao 100 numeros
>>
>>Umas sequencias possiveis seriam
>>
>>50s; 25s; 13s; 7n; 10s; 8n; 9s -> 8
>>50s; 25s; 13s; 7n; 10s; 8n; 9n -> 9
>>
>>25s = é menor que 25? Sim
>>7n = é menor que 7? Nao
>>
>>
>>Alek
>>
>>At 21:01 14/04/01 -0400, you wrote:
>>>     Pensei num número inteiro no intervalo de 1 até 100 e você deve
>>> descobrir
>>>qual            é. Para ajudar, responderei, apenas com sim ou não, a
>>>qualquer pergunta.
>>>     Qual é o menor número de perguntas que permite descobrir o número?
>>
>