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 =========================================================================