[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] PELO SIM, PELO NÃO!
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)
> > 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.
> >
>
> __________________________________________________
> Converse com seus amigos em tempo real com o Yahoo!
> Messenger
> http://br.download.yahoo.com/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
>
=========================================================================
>
__________________________________________________
Converse com seus amigos em tempo real com o Yahoo! Messenger
http://br.download.yahoo.com/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
=========================================================================