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 <[EMAIL PROTECTED]> > 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" <[EMAIL PROTECTED]> > > 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 =========================================================================