Brevemente

Os chapéus dos prisioneiros

Os chapéus dos prisioneiros

30 prisioneiros são informados de que serão colocados em fila e colocarão um chapéu na cabeça de cada pessoa, branco ou preto, sem especificar quantos bonés serão usados ​​em cada cor. Cada prisioneiro verá apenas os chapéus dos prisioneiros à sua frente, mas não os dele ou os que estão atrás.

Um guarda perguntará a cada um dos prisioneiros, sucessivamente, começando no último da fila (quem vê tudo, exceto o dele) até o primeiro (quem não vê nenhum) de que cor é seu chapéu. Os presos só podem responder em preto ou branco: se tiverem sucesso, são libertados e, se não, são executados. Todos os presos podem ouvir as respostas antes deles. Os prisioneiros não podem acenar, tocar os outros, ou dar pistas com o tom ou o volume da voz ... devem responder em preto ou branco da maneira mais asséptica possível, porque se os carcereiros detectassem algum truque dos mencionados, matariam todos.

Antes de fazer isso, os prisioneiros, que sabem o teste a que serão submetidos, mas não naturalmente de que cor serão seus chapéus, têm tempo para conversar e pensar em uma estratégia de grupo.

Você consegue pensar em alguma estratégia para salvar o maior número possível de prisioneiros?

Solução

É possível salvar com segurança todos, exceto o último da fila, com 50% de chance de salvar.

A estratégia seguida pelos prisioneiros consiste em "codificar" a paridade de uma das duas cores dos chapéus na fila. Assim, por exemplo, eles podem concordar que o último na fila (quem será o primeiro a dizer a cor do chapéu e não saberá o que será) dirá "branco" se o número total de chapéus brancos que você vê for par ou dizer "preto" Se o número total de chapéus brancos que você vê for ímpar.

Imagine que o primeiro veja 25 bonés brancos, que é um número ímpar. Ele não sabe qual é a cor dele, então não pode ter certeza do que tem a dizer para se salvar, mas como a quantidade de chapéus brancos que vê é estranha e ele chegou a um acordo com seus colegas de equipe, ele diz "preto".

O segundo, como ele ouviu "preto", sabe que o total de bonés brancos que o primeiro viu é ímpar, então ele os conta e se ele vê uma quantia par, seu boné é branco e, se for ímpar, seu boné é preto . Então ele diz isso.

O terceiro sabe que, originalmente, a quantidade é ímpar (porque a primeira informação é que a cor é preta, caso contrário, seria par). Se o que está à sua frente disse branco, contando o dele, deve haver uma quantia par e, se ele disse preto, estranho. Ao estudar a paridade daqueles que ele vê, ele pode saber de que cor é. Preto, se as informações que você calcula corresponderem ao que você vê, branco caso contrário.

Em resumo, a informação que o primeiro transmite é a paridade do número de alvos que ele vê (preto é ímpar, branco é par). Cada um deve mudar a paridade de ímpar para par cada vez que um dos prisioneiros com quem ele fala diz "branco" e conta os que vê. Se a paridade que ele calcula corresponde à informação que recebe, seu chapéu é preto e, se não corresponder, é branco.

Não existe um sistema melhor, já que não há como o primeiro saber a cor do seu chapéu, então ele terá 50% de chance de falhar, siga a estratégia seguida.