Re: [obm-l] PELO SIM, PELO NÃO!
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
Re: [obm-l] PELO SIM, PELO NÃO!
On Sun, Sep 18, 2005 at 09:20:33PM +, Rogerio Ponce wrote: Olá Nicolau, a primeira resposta de um desonesto pode ser o que ele preferir (verdadeira ou mentirosa), e a partir daí, ele sempre inverte, conforme o enunciado esclareceu perfeitamente. Repare que se na pergunta atual ele for mentiroso, então na próxima ele seria verdadeiro. Como na próxima ele me responderia SIM (pois estaria sendo verdadeiro) , então ele me diz (na pergunta atual) um NÃO, pois no momento ele é mentiroso. Se no entanto, ele no momento for verdadeiro, então , na próxima pergunta ele seria mentiroso , e diria NÃO . E é isso que ele me conta na pergunta atual, pois estará sendo verdadeiro. Portanto, o mentiroso sempre responderá NÃO àquela pergunta longa, enquanto o honesto sempre responderá SIM. Você tem toda a razão. Eu devo ter lido mal ou entendido mal o que você escreveu quando mandei a mensagem anterior. Sinto muito. []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 =
Re: [obm-l] PELO SIM, PELO NÃO!
Professor Nicolau: Em continuidade, percebi que o segundo e-mail enviado pelo senhor sobre o assunto é a resposta ao meu questionamento. De qualquer forma, obrigado. João. Nicolau C. Saldanha [EMAIL PROTECTED] Enviado Por: [EMAIL PROTECTED] 18/09/2005 07:56 Favor responder a obm-l Para: obm-l@mat.puc-rio.br cc: Assunto: Re: [obm-l] PELO SIM, PELO NÃO! On Fri, Sep 16, 2005 at 10:50:57AM -0400, [EMAIL PROTECTED] wrote: O não-entendimento é referente ao trecho em azul, pois, creio que o primeiro parágrafo é suficiente a refutação. Em azul para você. Não suponha que todo mundo veja as mensagens com as mesmas cores que você: isto é falso para mim e acho que muito longe de ser verdade para a maioria. Ou seja: sinto muito, não entendi nada do que você tentou perguntar. []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 =
Re: [obm-l] PELO SIM, PELO NÃO!
On Fri, Sep 16, 2005 at 05:35:18PM +, Rogerio Ponce wrote: 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. Acho que voce está supondo que a primeira resposta de um desonesto é sempre falsa. Eu não interpretei o enunciado desta forma (nem, acho, a maioria dos outros que comentaram a questão). Se for assim a sua solução é correta e o problema todo fica bem mais fácil. []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 =
Re: [obm-l] PELO SIM, PELO NÃO!
On Fri, Sep 16, 2005 at 10:50:57AM -0400, [EMAIL PROTECTED] wrote: O não-entendimento é referente ao trecho em azul, pois, creio que o primeiro parágrafo é suficiente a refutação. Em azul para você. Não suponha que todo mundo veja as mensagens com as mesmas cores que você: isto é falso para mim e acho que muito longe de ser verdade para a maioria. Ou seja: sinto muito, não entendi nada do que você tentou perguntar. []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 =
Re: [obm-l] PELO SIM, PELO NÃO!
Olá Nicolau, a primeira resposta de um desonesto pode ser o que ele preferir (verdadeira ou mentirosa), e a partir daí, ele sempre inverte, conforme o enunciado esclareceu perfeitamente. Repare que se na pergunta atual ele for mentiroso, então na próxima ele seria verdadeiro. Como na próxima ele me responderia "SIM" (pois estaria sendo verdadeiro) , então ele me diz (na pergunta atual) um "NÃO", pois no momento ele é mentiroso. Se no entanto, ele no momento for verdadeiro, então , na próxima pergunta ele seria mentiroso , e diria "NÃO" . E é isso que ele me conta na pergunta atual, pois estará sendo verdadeiro. Portanto, o mentiroso sempre responderá NÃOàquela pergunta longa, enquanto o honesto sempre responderá SIM. []s Rogerio Ponce. "Nicolau C. Saldanha" [EMAIL PROTECTED] escreveu: On Fri, Sep 16, 2005 at 05:35:18PM +, Rogerio Ponce wrote: 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.Acho que voce está supondo que a primeira resposta de um desonestoé sempre falsa. Eu não interpretei o enunciado desta forma (nem, acho,a maioria dos outros que comentaram a questão). Se for assim a suasolução é correta e o prob! lema todo fica bem mais fácil.[]s, N.__Converse com seus amigos em tempo real com o Yahoo! Messenger http://br.download.yahoo.com/messenger/
Re: [obm-l] PELO SIM, PELO NÃO!
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 =
Re: [obm-l] PELO SIM, PELO NÃO!
Professor Nicolau ou professor Gugu: Estou reestudando a questão desde o princípio, e já surgiu-me um não-entendimento, o qual transcrevo a seguir. Na primeira mensagem do Professor Nicolau, este colocou: “Eu discordo desta interpretação. Digamos que os candidatos estejam arrumados assim: d,d,h,d,d (onde h é o honesto e d não) e que você se faça esta pergunta. Ao primeiro da fila. Mesmo se interpretarmos que ele já decidiu que é hora de mentir e que perguntado diretamente ele responderá h,h,d,h,h, ele pode responder, por exemplo, “h,d,h,h,h”: ele estará mentindo e você não descobriu nada (ou tira conclusão errada). Acho que esta solução se aplica a perguntas com resposta “sim ou “não” e mesmo assim não tenho certeza se se aplica a este problema. Não entendo que o enunciado deixe claro que exista uma “hora de mentir” predeterminada ante de você formular a primeira pergunta. Ou seja, os desonestos podem decidir se vão mentir ou não na primeira pergunta em função da pergunta, arruinando este truque.” O não-entendimento é referente ao trecho em azul, pois, creio que o primeiro parágrafo é suficiente a refutação. Já o trecho em azul não se assemelha a esse primeiro parágrafo e, assim, não faz parte da refutação. De outra forma, creio eu um pouco confuso: o momento de decidir se vão mentir ou não na primeira pergunta é assunto distinto da forma como podem mentir. Estou certo nisso? Desde já, muito grato, João.
Re: [obm-l] PELO SIM, PELO NÃO!
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) 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 =
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 [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) 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.
Re: [obm-l] PELO SIM, PELO NÃO!
Caro Jorge Luis, Tem uma solução mais ou menos clássica com uma pergunta só: escolha um cara qualquer e pergunte:Se eu perguntasse a você sobre cada uma dessas 5 pessoas (incluindo você) se são honestas ou não, o que você responderia ? Se nesse momento ele for dizer a verdade, vai indicar o honesto corretamente. Se ele for mentir sistematicamente nessa resposta, ele responderia errado sobre todas as pessoas, caso perguntado diretamente sobre se são honestas ou não. Como ele é perguntado sobre o que responderia, ao mentir nessa resposta ele diria a informação correta. Assim, de qualquer jeito você obteria a informação correta. É claro que você pode achar que essa solução está meio roubada, e que devemos colocar restrições sobre que tipo de pergunta pode ser feito - por exemplo, o problema é diferente se só admitirmos perguntas cujas possíveis respostas sejam sim ou não. Abraços, Gugu Quoting Jorge Luis Rodrigues e Silva Luis [EMAIL PROTECTED]: Perdão! Nicolau e demais colegas pela suposta arrogância que não houve intenção de provocação. Quanto ao desenho anexo no enunciado do problema, constam 12 quadrados (quarteirões) com suas 4 ruas horizontais e 5 ruas verticais. E aí vem a inevitável pergunta: Se vocês fossem da comissão do vestibular da FGV-SP, que resposta considerariam como a correta: 10, 20, 35, ? Cinco pessoas estão em uma sala. Uma delas é um sujeito honesto, que sempre diz sempre a verdade. As outras quatro alternam uma mentira e uma verdade e podem começar por qualquer uma das duas. Todos sabem quem é o sujeito honesto, menos você. Qual é o número mínimo de perguntas necessário para descobrir o honesto? NOTA: Achei muito simpático o termo nosso herói ... Abraços! _ MSN Messenger: converse online com seus amigos . http://messenger.msn.com.br = 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 = This message was sent using IMP, the Internet Messaging Program. = 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 =
Re: [obm-l] PELO SIM, PELO NÃO!
On Wed, Sep 14, 2005 at 01:54:35PM -0300, [EMAIL PROTECTED] wrote: Caro Jorge Luis, Tem uma solução mais ou menos clássica com uma pergunta só: escolha um cara qualquer e pergunte:Se eu perguntasse a você sobre cada uma dessas 5 pessoas (incluindo você) se são honestas ou não, o que você responderia ? Se nesse momento ele for dizer a verdade, vai indicar o honesto corretamente. Se ele for mentir sistematicamente nessa resposta, ele responderia errado sobre todas as pessoas, caso perguntado diretamente sobre se são honestas ou não. Como ele é perguntado sobre o que responderia, ao mentir nessa resposta ele diria a informação correta. Assim, de qualquer jeito você obteria a informação correta. Eu discordo desta interpretação. Digamos que os candidatos estejam arrumados assim: d,d,h,d,d (onde h é honesto e d não) e que você se faça esta pergunta ao primeiro da fila. Mesmo se interpretarmos que ele já decidiu que é hora de mentir e que perguntado diretamente ele responderia h,h,d,h,h, ele pode responder, por exemplo, h,d,h,h,h: ele estará mentindo e você não descobriu nada (ou tira a conclusão errada). Acho que esta solução se aplica a perguntas com resposta Sim ou Não e mesmo assim não tenho certeza se se aplica a este problema. Não entendo que o enunciado deixe claro que exista uma hora de mentir predeterminada antes de você formular a primeira pergunta. Ou seja, os desonestos podem decidir se vão mentir ou não na primeira pergunta em função da pergunta, arruinando este truque. []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 =
Re: [obm-l] PELO SIM, PELO NÃO!
Caro Nicolau, Eu concordo que a minha solução admite críticas nessa linha, mas o Elon, por exemplo, argumenta do mesmo jeito sobre um problema análogo num livro dele (supondo que um cara que vai mentir numa resposta mente sobre tudo). De qualquer jeito eu acho que a melhor conclusão é que o problema está mal formulado, e seria melhor especificar que tipo de pergunta pode ser feita. Por outro lado, eu não entendi bem a sua última objeção: se os desonestos decidiremhttp://www.impa.br/biblioteca/index.html, em função da minha pergunta, entre dizer a verdade em toda a sua resposta ou só fazer afirmações falsas em sua resposta então a minha solução funciona. Seria interessante saber a opinião do Jorge Luiz sobre se as respostas devem ser sempre sim ou não e sobre se mentirosos mentem consistentemente ou podem mentir parcialmente no caso em que respostas mais complicadas sejam admissíveis. Abraços, Gugu Quoting Nicolau C. Saldanha [EMAIL PROTECTED]: On Wed, Sep 14, 2005 at 01:54:35PM -0300, [EMAIL PROTECTED] wrote: Caro Jorge Luis, Tem uma solução mais ou menos clássica com uma pergunta só: escolha um cara qualquer e pergunte:Se eu perguntasse a você sobre cada uma dessas 5 pessoas (incluindo você) se são honestas ou não, o que você responderia ? Se nesse momento ele for dizer a verdade, vai indicar o honesto corretamente. Se ele for mentir sistematicamente nessa resposta, ele responderia errado sobre todas as pessoas, caso perguntado diretamente sobre se são honestas ou não. Como ele é perguntado sobre o que responderia, ao mentir nessa resposta ele diria a informação correta. Assim, de qualquer jeito você obteria a informação correta. Eu discordo desta interpretação. Digamos que os candidatos estejam arrumados assim: d,d,h,d,d (onde h é honesto e d não) e que você se faça esta pergunta ao primeiro da fila. Mesmo se interpretarmos que ele já decidiu que é hora de mentir e que perguntado diretamente ele responderia h,h,d,h,h, ele pode responder, por exemplo, h,d,h,h,h: ele estará mentindo e você não descobriu nada (ou tira a conclusão errada). Acho que esta solução se aplica a perguntas com resposta Sim ou Não e mesmo assim não tenho certeza se se aplica a este problema. Não entendo que o enunciado deixe claro que exista uma hora de mentir predeterminada antes de você formular a primeira pergunta. Ou seja, os desonestos podem decidir se vão mentir ou não na primeira pergunta em função da pergunta, arruinando este truque. []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 = This message was sent using IMP, the Internet Messaging Program. = 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 =
Re: [obm-l] PELO SIM, PELO NÃO!
On Wed, Sep 14, 2005 at 04:35:28PM -0300, [EMAIL PROTECTED] wrote: Por outro lado, eu não entendi bem a sua última objeção: se os desonestos decidirem, em função da minha pergunta, entre dizer a verdade em toda a sua resposta ou só fazer afirmações falsas em sua resposta então a minha solução funciona. Acho que não. Suponha que um desonesto pode mentir ou dizer a verdade, a única restrição sendo que ele deve alternar entre mentiras e verdades. Ele decide que vai mentir ou dizer a verdade na primeira pergunta em função da pergunta de uma forma complicada qualquer que inclui os seguintes casos particulares: Se a pergunta for Você é honesto?, o desonesto vai MENTIR. Se a pergunta for Se eu perguntasse a você 'Você é honesto?', o que você responderia?, o desonesto vai DIZER A VERDADE. Por exemplo, o critério dele pode ser o seguinte: se a última letra da pergunta for abcdefghijklm, ele dirá a verdade. Se for nopqrstuvwxyz, ele mentirá. Gugu encontra este desonesto e faz a pergunta: Se eu perguntasse a você 'Você é honesto?', o que você responderia?. O desonesto (que não é burro) pensa: se ele me fizesse a pergunta curta eu mentiria e diria SIM. Como eu vou dizer a verdade para a pergunta longa (a que Gugu realmente fez) vou responder... SIM!. Gugu não pode com isso deduzir nada sobre a honestidade do cara com esta primeira pergunta e resposta. Claro que se Gugu repetir a mesma pergunta a situação já é outra, pois agora o desonesto está obrigado a mentir. []s, N. PS: Onde foi, exatamente, que o Elon discutiu este tipo de coisa? = 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 =
Re: [obm-l] PELO SIM, PELO NÃO!
ei pessoal, tentem resolver considerando perguntas cuja resposta é apenas SIM ou NAO e os mentirosos nao sao pessoas e sim moedas nao viciadase vejam se conseguem algo melhor do que eu fiz... --- Nicolau C. Saldanha [EMAIL PROTECTED] escreveu: On Wed, Sep 14, 2005 at 12:29:42PM -0400, Qwert Smith wrote: Sao necessarias pelo menos 2 perguntas. Escolha um dos individuos e peca a ele que identifique os desonestos. Logo em seguida faca o mesmo pedido ao mesmo individuo. Se ele for o honsto suas respostas seram iguais e ele nao se acusa nunca. Caso contrario suas respostas serao diferentes. Basta entao vc se valer da resposta em que ele se acusa como um dos desonestos, ja que nessa resposta ele esta falando a verdade. Acho que n�o. Se as perguntas forem dirigidas a A e o honesto for B, ele pode dar as duas seguintes respostas (em qualquer ordem): O honesto � o B. (verdade) O honesto � o C. (mentira) Voc� s� pode concluir que o honesto � ou B ou C. []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 = O Binômio de Newton é tão belo como a Vênus de Milo. O que há é pouca gente para dar por isso... Fernando Pessoa - Poesias de Alvaro Campos _ As informações existentes nessa mensagem e no(s) arquivo(s) anexado(s) são para uso restrito, sendo seu sigilo protegido por lei. Caso não seja destinatário, saiba que leitura, divulgação ou cópia são proibidas. Favor apagar as informações e notificar o remetente. O uso impróprio será tratado conforme as normas da empresa e a legislação em vigor. Agradecemos sua colaboração. The information mentioned in this message and in the archives attached are of restricted use, and its privacy is protected by law. If you are not the addressee, be aware that reading, disclosure or copy are forbidden. Please delete this information and notify the sender. Inappropriate use will be tracted according to company's rules and valid laws. Thank you for your cooperation. ___ Yahoo! Messenger com voz: PROMOÇÃO VOCÊ PODE LEVAR UMA VIAGEM NA CONVERSA. Participe! www.yahoo.com.br/messenger/promocao = 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 =
Re: [obm-l] PELO SIM, PELO NÃO!
Olá Nicolau, sua solução ébonita porque resolve para qualquer número de pessoas. Mas, e se todos(como sugeriu o Chicão) só puderemresponder "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. []'s Rogerio Ponce "Nicolau C. Saldanha" [EMAIL PROTECTED] escreveu: On Wed, Sep 14, 2005 at 05:06:24PM -0300, Nicolau C. Saldanha wrote: On Wed, Sep 14, 2005 at 12:29:42PM -0400, Qwert Smith wrote: Sao necessarias pelo menos 2 perguntas.Escolha um dos individuos e peca a ele que identifique os desonestos. Logo em seguida faca o mesmo pedido ao mesmo individuo.Se ele for o honsto suas respostas seram iguais e ele nao se acusa nunca. Caso contrario suas respostas serao diferentes. Basta entao vc se valer da resposta em que ele se acusa como um dos desonestos, ja que nessa resposta ele esta falando a verdade. Acho que nao. Se as perguntas forem dirigidas a A e o honesto for B, ele pode dar as duas seguintes respostas (em qualquer ordem): "O honesto e o B." (verdade) "! O honesto e o C." (mentira) Voce so pode concluir que o honesto e ou B ou C.Só para dar um tom mais positivo às minhas contribuições:você sempre pode resolver o problema com as 3 seguintes perguntas:"Quem é o honesto?", "Quem é o honesto?", "Você é honesto?".Se as duas primeiras perguntas receberem a mesma resposta,nosso interlocutor é honesto e a terceira pergunta é supérflua.Se as duas primeiras perguntas receberem respostas diferentesentão sabemos que nosso interlocutor não é honesto e portantocom a terceira resposta ele indicará qual das duas primeirasrespostas era a correta.[]s, N.__Converse com seus amigos em tempo real com o Yahoo! Messenger http://br.download.yahoo.com/messenger/
Re: [obm-l] PELO SIM, PELO NÃO!
Estou meio enferujado pra estatistica mas vou tentar...Se nao houver um pulo do gato ou algo que nao me ocorreu, faria assim: I-pergunte algo que é verdade a cada um cuja resposta ou è SIM ou é NAO II- o que é honesto sempre vai dizer sim, os 4 desonestos vao variar aleatoriamente... III- Vc saberá quem é desonesto pelas respostas NAO... Qual o numero esperado de vezes tal que cada um dos quatro desonestos terao dito pelo menos um NAO em suas respostas??? Cada desonesto é uma distribuiçao geometrica de p = 1/2... Se chamarmos de X, Y , Z ,W a variavel aleatoria de cada desonesto no caso de se dizer o primeiro NAO temos: E(X) = E(Y)= E(Z)= E(W) = 1/(1/2) = 2 Assim o que queremos é E(X+Y+Z+W)= E(X)+E(Y)+E(Z)+E(W) = 8 ou seja, devemos esperar que com 8 perguntas desse tipo poderemos determinar quem seja o honesto.. Outra coisa que me ocorreu exatamente agora é perguntar a cada um quem sao os desonestos da sala, talvez diminua o numero de perguntas pois o honesto nunca iria se referir a ele e suas respostas seriam constantes enquanto a chance de variaçao das respostas dos outros é bastante alta e incluria eles mesmos nas respostas, talvez dessa forma duas perguntas e no maximo 3 mate a charadamas deixo essa pra vc analizar JorgeValeu ;) Cinco pessoas estão em uma sala. Uma delas é um sujeito honesto, que sempre diz sempre a verdade. As outras quatro alternam uma mentira e uma verdade e podem começar por qualquer uma das duas. Todos sabem quem é o sujeito honesto, menos você. Qual é o número mínimo de perguntas necessário para descobrir o honesto? NOTA: Achei muito simpático o termo nosso herói ... Abraços! _ MSN Messenger: converse online com seus amigos . http://messenger.msn.com.br = 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 = O Binômio de Newton é tão belo como a Vênus de Milo. O que há é pouca gente para dar por isso... Fernando Pessoa - Poesias de Alvaro Campos _ As informações existentes nessa mensagem e no(s) arquivo(s) anexado(s) são para uso restrito, sendo seu sigilo protegido por lei. Caso não seja destinatário, saiba que leitura, divulgação ou cópia são proibidas. Favor apagar as informações e notificar o remetente. O uso impróprio será tratado conforme as normas da empresa e a legislação em vigor. Agradecemos sua colaboração. The information mentioned in this message and in the archives attached are of restricted use, and its privacy is protected by law. If you are not the addressee, be aware that reading, disclosure or copy are forbidden. Please delete this information and notify the sender. Inappropriate use will be tracted according to company's rules and valid laws. Thank you for your cooperation. ___ Yahoo! Messenger com voz: PROMOÇÃO VOCÊ PODE LEVAR UMA VIAGEM NA CONVERSA. Participe! www.yahoo.com.br/messenger/promocao = 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 =
Re: [obm-l] PELO SIM, PELO NÃO!
On Mon, Sep 12, 2005 at 12:39:54PM +, Jorge Luis Rodrigues e Silva Luis wrote: Perdão! Nicolau e demais colegas pela suposta arrogância que não houve intenção de provocação. Quanto ao desenho anexo no enunciado do problema, constam 12 quadrados (quarteirões) com suas 4 ruas horizontais e 5 ruas verticais. E aí vem a inevitável pergunta: Se vocês fossem da comissão do vestibular da FGV-SP, que resposta considerariam como a correta: 10, 20, 35, ? Com este enunciado acompanhado de desenho fica claro para mim que a resposta correta é binomial(9,4) = 35. Estou interpretando que o desenho é assim, e que nosso herói deve ir de A até B. A---c---d---e---f | | | | | | | | | | g---h---i---j---k | | | | | | | | | | l---m---n---o---p | | | | | | | | | | q---r---s---t---B Os caminhos são: AcdefkpB, AcdejkpB, AcdejopB, AcdejotB, AcdijkpB, AcdijopB, AcdijotB, AcdunopB, AcdinotB, AcdinstB, AchijkpB, AchijopB, AchijotB, AchinopB, AchinotB, AchinstB, AchmnopB, AchmnotB, AchmnstB, AchmrstB, AghijkpB, AghijopB, AghijotB, AghinopB, AghinotB, AghinstB, AghmnopB, AghmnotB, AghmnstB, AghmrstB, AglmnopB, AglmnotB, AglmnstB, AglmrstB, AglqrstB. []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 =
