Olá pessoal,
quase não aguento mais esse problema, mas não dá para
ignorar que minhas perguntas podem ser simplificadas,
da seguinte forma:
Pergunte a "A":
- Se daqui a duas perguntas, eu lhe perguntar
"Existe um honesto entre tais fulanos?"
você me responderá um SIM?
A resposta obtida sempre será a indicação correta, e a
pesquisa binária pode ser feita sem dificuldade
alguma.
Portanto, com 3 perguntas assim, é possível localizar
o honesto dentre 8 participantes.
[]'s
Rogerio Ponce
PS: Juro que não escrevo mais nada a respeito desta
questão.
---------------------------------
--- Rogerio Ponce escreveu:
> Olá Nicolau,
> na verdade, dá para superpor duas vezes (em cada
> pergunta) a política que eu sugeri, de modo a sempre
> obter a verdade.
>
> Em outras palavras, se com 2 perguntas aninhadas, a
> gente consegue um "inversor", com 4 perguntas
> aninhadas, a gente sempre obtém a verdade.
>
> E então, mesmo sem a auto-referência, a gente
> consegue
> distinguir o honesto entre 8 pessoas, fazendo uma
> pesquisa binária desde o início.
>
> O exemplo é um "pouquinho" enrolado, mas acho que
> funciona:
>
> Pergunte a "A":
> - Se minha próxima pergunta a você for
> "Se minha próxima pergunta a você for
> ""Se minha próxima pergunta a você for
> """Existe um honesto entre tais
> fulanos?"""
> você me responderá um SIM?""
> você me responderá um SIM?"
> você me responderá um SIM?
>
>
> []s,
> Rogerio Ponce
>
>
>
> --- Rogerio Ponce <rogerioponce-obm@yahoo.com.br>
> escreveu:
>
> > Olá Nicolau,
> > esse solução (resolvendo para 8) também é
> > interessante
> > - aliás, é A MAIS INTERESSANTE -, apesar de eu
> > também
> > achar um pouco "apelativa" pela auto-referência.
> >
> >
> > O que imaginei anteriormente, resolveria apenas
> para
> > 5
> > participantes (A,B,C,D,E), da seguinte forma:
> >
> > Pergunte a "A":
> > - Se minha próxima pergunta a você for "Existe
> > apenas
> > 1 honesto entre vocês?" , você me responderá um
> > "SIM"?
> >
> > O honesto responderá SIM, e um desonesto
> responderá
> > NÃO. Supondo que "A" seja desonesto, agora você
> faz
> > a
> > seguinte pergunta a "A":
> >
> > - Se minha próxima pergunta a você for "O honesto
> se
> > encontra entre B e C?" , você me responderá um
> > "SIM"?
> >
> > Se a resposta for "NÃO" , então o honesto é B ou
> C.
> > Caso contrário, o honesto é D ou E.
> > Supondo que tenha respondido "NÃO", agora você
> > pergunta a "A":
> >
> > - Se minha próxima pergunta a você for "O honesto
> é
> > B?", você me responderá um "SIM"?
> >
> > Se a resposta for "NÃO" , o honesto é B, caso
> > contrário é C.
> >
> > As outras derivações se resolvem do mesma modo,
> > sempre
> > usando a "dupla filtragem pelo desonesto", de
> forma
> > a
> > sempre obter a resposta invertida.
> >
> >
> > Mas como falei, essa minha solução ficou "na
> > poeira",
> > pois só consegue resolver para 5 pessoas...
> >
> > []s,
> > Rogerio Ponce.
> >
> >
> > --- "Nicolau C. Saldanha" <nicolau@mat.puc-rio.br>
> > escreveu:
> >
> > > 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)
>
=== message truncated ===
_______________________________________________________
Novo Yahoo! Messenger com voz: ligações, Yahoo! Avatars, novos emoticons e muito mais. Instale agora!
www.yahoo.com.br/messenger/
=========================================================================
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
=========================================================================