O problema dos chapéus
Dentro do estudo de paridade, temos um problema de uma fama elementar, o problema dos chapéus. Se trata de um problema de lógica que representa uma estratégia em um jogo cooperativo.
Problema 1.6 Imagine que 10 prisioneiros estejam trancados em uma cela quando chega um carcereiro com o seguinte comunicado:
- Amanhã todos vocês passarão por um teste. Todos vocês carão em la indiana e serão colocados chapéus nas cabeças de cada um de vocês. Cada um poderá ver os chapéus dos que estarão a sua frente, porém não poderão ver os chapéus dos que estão atrás, nem o seu próprio chapéu. Os chapéus serão pretos ou brancos. Feito isso, será perguntado a cada um de vocês, do último para o primeiro, em ordem, qual a cor do seu chapéu. Se a pessoa errar a cor do seu chapéu, será morta.
Será que os prisioneiros podem montar uma estratégia para salvar pelo menos 9 deles?
Demonstração 2. Vamos primeiramente pensar no Problema: Para iniciarmos a discussão do problema, vejamos que a primeira ideia de uma solução seria a seguinte:
ˆ Cada um dos 10 prisioneiros fala a cor do chapéu que está imediatamente a sua frente.
Esta é a ideia que todos têm inicialmente, mas logo verica-se que esta estratégia não funciona, pois basta que as cores dos chapéus estejam alternadas para a estratégia não funcionar. (Lembre-se estamos procurando uma estratégia que independa da escolha dos chapéus.)
Então devemos pensar de maneira mais profunda. Veja que durante o teste, cada um dos prisioneiros pode falar apenas uma entre duas palavras que são: preto ou branco. Isto corresponde a um sistema de linguagem binário. Outras formas de linguagem binária são: sim ou não, zero ou um, par ou ímpar. E é exatamente esta analogia que vamos utilizar para montar nossa estratégia, que será a seguinte:
O último da fila deve olhar para frente e contar o número de chapéus pretos. Se este número for ímpar, ele deve gritar preto. Caso contrário, ele deve gritar branco. Com isso, todos ficam sabendo a paridade da quantidade de chapéus pretos que existe entre os nove primeiros dafila.
Agora, o penúltimo vai olhar para frente e ver a quantidade de chapéus pretos. Se a paridade continuar a mesma informada pelo último, então seu chapéu é branco. Se mudar ele pode concluir que seu chapéu é preto. E isto pode ser feito para todos os demais membros da la, pois todos saberão a cor dos chapéus dos anteriores (tirando a cor do chapéu do último) e a paridade do chapéus pretos que existem entre os nove primeiros.
Portanto, é possível salvar os nove primeiros, enquanto o último pode ser salvo, se ele tiversorte!
EXERCÍCIOS:
1. Após a leitura do problema dos chapéus faça um resumo sobre o que você compreendeu? É possivél encontrar uma estratégia de resolução mais simples? Justifique.
Soluções para a tarefa
Resposta:
Bem, vamos começar a discutir o problema da seguinte maneira: Será que se eles combinarem de cada um deles falar a cor do chapéu que está imediatamente a sua frente eles podem salvar a maior parte do bando?
Esta é a ideia que todos têm inicialmente, mas logo verifica-se que esta estratégia não funciona, pois basta que as cores dos chapéus estejam alternadas para a estratégia na funcionar. (Lembre-se estamos procurando uma estratégia que independa da escolha dos chapéus.)
Então devemos pensar de maneira mais profunda. Veja que durante o teste, cada um dos prisioneiros pode falar apenas uma entre duas palavras que são: preto ou branco. Isto corresponde a um sistema de linguagem binário. Outras formas de linguagem binária são: sim e não, zero ou um, par ou ímpar. E é exatamente esta analogia que vamos utilizar para montar nossa estratégia. Que será a seguinte:
O último da fila deve olhar para frente e contar o número de chapéus pretos. Se este número for ímpar, ele deve gritar preto. Caso contrário, ele deve gritar branco. Com isso, todos ficam sabendo a paridade da quantidade de chapéus preto que existe entre os nove primeiros da fila.
Agora, o penúltimo vai olhar para frente e ver a quantidade de chapéus pretos. Se a paridade continuar a mesma informada pelo último, então seu chapéu é branco. Se mudar ele pode concluir que seu chapéu é preto. E isto pode ser feito para todos os demais membros da fila, pois todos saberão a cor dos chapéus dos anteriores (tirando a cor do chapéu do último) e a paridade do chapéus pretos que existem entre os nove primeiros.
Portanto, é possível salvar os nove primeiros, enquanto o último pode ser salvo, se ele tiver sorte!