Re: [obm-l] PELO SIM, PELO NÃO!

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Wed, Sep 14, 2005 at 09:59:01PM -0300, Rogerio Ponce wrote:
> Olá Nicolau,
> sua solução é bonita porque resolve para qualquer número de pessoas.
> Mas, e se todos (como sugeriu o Chicão) só puderem responder "sim" ou "não" a
> qualquer questão?
>  
> Parece-me que - neste caso de apenas 5 participantes - ainda é possível
> resolver com apenas 3 perguntas.

Acho que dá até com 8 participantes, mas só com um pouco de apelação.
Digamos que os participantes se chamam
000, 001, 010, 011, 100, 101, 110, 111.
As perguntas seriam:

"Considere a seguinte afirmação:
'A sua resposta para esta pergunta será verdadeira se e somente se
o primeiro algarismo do nome do honesto é 1.';
a afirmação é verdadeira?"

É fácil verificar que se a resposta for SIM (resp. NÃO)
então o primeiro algarismo do nome do honesto é 1 (resp. 0),
independentemente da resposta ser verdadeira ou falsa.
Isto é parecido com o truque apresentado pelo Gugu mas um pouco diferente
(e eu acho que agora correto). Note que a pergunta é duplamente
problemática: é auto-referente e pergunta sobre o futuro.
É muito fácil com este tipo de 'golpe baixo' produzir perguntas
irrespondíveis, como
"Considere a seguinte afirmação:
'A sua resposta para esta pergunta será verdadeira se e somente se
a sua resposta será NÃO.';
e afirmação é verdadeira?"

Naturalmente, a segunda e terceira pergunta são, respectivamente:

"Considere a seguinte afirmação:
'A sua resposta para esta pergunta será verdadeira se e somente se
o segundo algarismo do nome do honesto é 1.';
e afirmação é verdadeira?"

"Considere a seguinte afirmação:
'A sua resposta para esta pergunta será verdadeira se e somente se
o terceiro algarismo do nome do honesto é 1.';
a afirmação é verdadeira?"

Note que com estas perguntas podem ser dirigidas a qualquer um.
Você determina quem é o honesto mas, paradoxalmente, fica eternamente
sem saber se as respostas que você ouviu eram verdadeiras ou falsas.

Acredito que sem este tipo de apelação é impossível resolver o problema
original, com 5 pessoas chamadas A, B, C, D, E.

De fato, três perguntas com resposta SIM ou NÃO criam 8 possíveis
resultados (isto é verdade mesmo se as perguntas dependerem das
respostas anteriores). Ora, sem algum tipo de apelação você esperaria
que ao resolver o problema descobrisse não apenas quem é o honesto,
mas se as pessoas com quem você falou estavam mentindo ou não.
Mesmo se você dirigir todas as perguntas à mesma pessoa (digamos, A)
isto criaria 9 casos:

A é honesto.
B é honesto e A respondeu VFV.
B é honesto e A respondeu FVF.
C é honesto e A respondeu VFV.
C é honesto e A respondeu FVF.
D é honesto e A respondeu VFV.
D é honesto e A respondeu FVF.
E é honesto e A respondeu VFV.
E é honesto e A respondeu FVF.

Ora, com 8 possíveis resultados é impossível decidir entre 9 casos.

[]s, N.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================