30 prisioneiros são colocados em fila cada um com um chapéu branco ou preto na cabeça. Eles não sabem a cor do chapéu que têm na cabeça, nem quantos chapéus existem de cada cor. Cada um dos prisioneiros consegue apenas ver os chapéus dos que estão à sua frente. Um guarda vai perguntar a cada um deles, começando no último da fila (aquele que pode ver todos os chapéus com excepção do próprio) e acabando no primeiro, qual a cor do chapéu que cada um possui. Os prisioneiros podem apenas responder ‘branco’ ou ‘preto’. Os que acertarem na cor do respectivo chapéu serão libertados, caso contrário serão executados. Cada um dos prisioneiros pode ouvir as respostas dos outros. O guarda só dirá no final quem respondeu correctamente.
Antes do teste começar os prisioneiros podem combinar qual a estratégia a seguir para garantir que o maior número de prisioneiros sobrevive.
Qual é a melhor estratégia? Quantos prisioneiros sobrevivem?
(Este problema aparece proposto no El País)
Eu penso que esta é a melhor estratégia (permite a sobrevivência em média de 25 prisioneiros, e no ,mínimo de 20):
ResponderEliminarCada um dos 10 primeiros prisioneiros (nº1 a 20) diz se a cor do chapéu de cada um dos 10 segundos (entre o prisioneiro nº11 e 20)é igual à cor do chapeu do 10º à sua frente. Usa a palavra "branco" para dizer que são iguais e "preto" se forem diferentes. Assim, por exemplo, se o nº prisioneiro disser branco, o 10+nº sabe que o seu chapéu é da mesma cor que o do 20+nº prisioneiro, cuja cor ele consegue ver. Depois basta ao 20+nº prisioneiro dizer a mesma cor que o 10+nº disse. No caso do prisioneiro n dizer preto, o 10+nº diz a cor oposta à do chapeu do 20+nº e o 20+nº diz a cor oposta à que o 10+n disse.
Assim sobrevivem sempre os 20 últimos prisioneiros, podendo cada um dos 10 primeiros sobreviver ou não consoante a sua sorte.
Um problema de paridade. Basta eles combinarem que o último iria indicar a cor predominantemente ímpar. Digamos que o último gritasse preto, o penúltimo olharia à sua frente e verificaria a paridade (par ou ímpar) dos pretos, se a paridade se mantivesse o seu chapéu seria branco, caso contrário seria preto, e assim por diante. Dessa forma, 29 prisioneiros seriam livres. E com muita sorte, o último!
ResponderEliminar