Siga-nos

Perfil

Expresso

Solução para o problema da semana “Um honesto entre mentirosos”

  • 333

Na sexta-feira colocámos AQUI o seguinte problema:

Há 10 pessoas numa sala. Um diz sempre a verdade. Os outros são mentirosos, cada um deles alterna sempre entre a verdade e mentira, embora não se saiba se começa por mentir ou dizer a verdade.

Cada um deles responde a cada pergunta com uma só palavra e sabem sempre qual é a resposta correta. Podemos também restringir o tipo de respostas que podem dar, se perguntarmos “De entre vocês os dez quem é o honesto?”, mesmo que esteja a mentir, essa pessoa diz realmente o nome de uma das pessoas na sala.

A questão era: qual o número mínimo de perguntas para descobrir o honesto?

Este problema está colocado, com uma solução num dos vídeos (pode vê-lo AQUI) do Salman Khan. Esta é uma versão ligeiramente modificada porque achámos que a original era um pouco ambígua.

Uma solução óbvia é perguntar repetidamente ao mesmo uma pergunta cuja resposta correta seja clara, por exemplo: “Quanto vale 2+2?”. Se a pessoa escolhida for o honesto vai responder sempre “quatro”, se não for, é fácil ver quando está a mentir. Depois é só perguntar “Quem é o honesto?” quando tivermos a certeza que ele vai falar verdade. Com esta estratégia, no pior dos cenários, podemos ter de chegar às três perguntas.

A solução do Saman Khan só tem duas perguntas, ele escolhe uma das pessoas e pergunta: -Tu és mentiroso?

Há duas possibilidades: se ele responder negativamente, quer dizer que ou é o honesto ou é um mentiroso que começou por mentir. De qualquer das formas fica a saber que da próxima vez vai dizer a verdade. Assim pergunta de novo ao mesmo: - Quem é o mentiroso? E obtém o nome do honesto.

Pode também acontecer que ele responda positivamente. Nesse caso fica a saber que se trata de um mentiroso que começou por falar a verdade, da próxima vez vai mentir. Assim, pergunta de novo ao mesmo: - De entre estas dez pessoas, quem mente? E obtém o nome do honesto.

Surpreendentemente, um dos nossos leitores apresentou uma solução com uma só pergunta. A pergunta é a seguinte:

“De entre estas dez pessoas, quem é mentiroso, se estiveres a mentir, e quem é o honesto, se estiveres a falar verdade?”

Embora seja um pouco rebuscada gramaticalmente, faz sentido do ponto de vista lógico. Trata-se da conjunção de duas frases, o que não viola as regras. Também condiciona as respostas aos nomes das dez pessoas, o que está dentro das regras. A grande novidade é que o tipo de resposta está condicionada ao facto de quem responde estar a falar verdade ou a mentir. Creio que podemos entender que esta é uma restrição de resposta, tal como a restrição às dez pessoas, e que um mentiroso tenha de acatar esta imposição.

Claramente que, se quem responde a esta pergunta estiver a falar verdade, independentemente de ser o honesto ou alguém que alterna entre mentira e verdade, vai ter de dar o nome do honesto. Por outro lado, se estiver a mentir, nunca poderia dizer o nome de um dos mentirosos, caso contrário estaria a responder de forma verdadeira à pergunta, logo só pode dar o nome do honesto. Parabéns jpa!