Execução de Prisioneiros em Fila

Infelizmente, a legislação de Problemópolis ainda prevê a pena de morte, e o rei atual é particularmente sanguinário: dez prisioneiros deverão ser executados hoje.

Por outro lado, o artigo sobre pena de morte contém um certo parágrafo, não visto na maioria dos outros países:

1. Toda vez que um certo número de prisioneiros tiver que ser executado, o seguinte procedimento deverá ser seguido. O carrasco os colocará em fila indiana, todos virados para a frente da fila, de modo que o último da fila veja todos os outros prisioneiros, o penúltimo veja todos exceto o último, e assim por diante: o prisioneiro no início da fila não verá ninguém. Em seguida, o carrasco lhes colocará chapéus pretos e brancos, da maneira que quiser, podendo até escolher aleatoriamente; a única restrição é que seja colocado exatamente um chapéu em cada condenado. Não deve ser permitido a nenhum deles ver seu próprio chapéu; apenas os chapéus dos prisioneiros que estão à sua frente, na fila.
2. O carrasco fará as execuções de trás para a frente da fila, começando com o prisioneiro que pode ver todos os outros. A cada um, antes de morrer, deve-se perguntar a cor de seu chapéu. Se responder corretamente, será poupado; incorretamente, e será morto. Todos os prisioneiros deverão ouvir, claramente, todas as respostas, bem como o resultado de cada uma (morte ou salvação).
3. Na noite anterior à execução, todos os prisioneiros deverão encontrar-se para discutir.
   

Que estratégia os dez prisioneiros devem adotar, para salvarem-se em maior número possível? No mínimo quantos serão salvos, no pior caso? E no melhor caso?

Se considerarmos Problemópolis como uma Atenas moderna, com sua preocupação com as coisas da mente, então Infinitópolis, cidade vizinha, certamente é Esparta: sua legislação é muito mais severa. Eis aqui os parágrafos correspondentes:

1. Em Infinitópolis, não será desperdiçado dinheiro público nas preparações para a execução de um número finito de pessoas. Somente infinitas pessoas são executadas de cada vez. Porém, devido a limitações de espaço, somente um infinito enumerável de pessoas serão executadas de cada vez.
2. Quando infinitos prisioneiros tiverem que ser executados, eles deverão ser postos em bijeção com os números naturais, configuração também conhecida como “fila indiana”. Todos os prisioneiros devem estar virados para o lado interminável da fila: o de número 1, último da fila, podendo ver todos os demais à sua frente; o de número 2, penúltimo, vendo todos exceto o de número 1, etc. Não haverá “primeiro da fila”: isto seria uma exaltação indevida do indivíduo, numa sociedade coletivista como a nossa.
3. O carrasco colocará um chapéu em cada prisioneiro, preto ou branco, como melhor lhe aprouver. A escolha poderá ser aleatória. Nenhum prisioneiro poderá ver nenhum chapéu, exceto os daqueles prisioneiros que estiverem à sua frente.
4. O carrasco iniciará a execução pelo fim da fila, no prisioneiro de número 1. A cada prisioneiro perguntará a cor de seu chapéu; matará os que errarem, e poupará os que acertarem. Não é permitido a nenhum prisioneiro ouvir as respostas dos outros, nem saber o resultado. Isto é assunto do Estado.
5. Na noite anterior à discussão, os prisioneiros poderão se reunir para discutir.

Como o leitor pode ver, em Infinitópolis a vida é mais difícil. Porém, graças a este ambiente hostil, a população evoluiu certas adaptações, que auxiliam a sobrevivência. Uma delas é excelente visão: o prisioneiro de número 1 consegue mesmo enxergar a fila toda, e cada um dos outros enxerga toda a parte que se estende à sua frente. Outra adaptação é a memória: cada infinitopolita consegue guardar uma quantidade ilimitada de informação.

Existe uma estratégia que os prisioneiros podem adotar, que garante mais do que 50% de sobrevivência?

(A questão de como definir porcentagens pro caso infinito é sutil; aqui há algumas possibilidades. Por exemplo, salvar todos os prisioneiros de número par seria admirável, mas ainda “50%” no sentido da Wikipedia. Salvar todos os prisioneiros, exceto aqueles cujo número é um quadrado perfeito, seria salvar “100%” — é, em conjuntos infinitos a probabilidade é um pouco diferente. Salvar todos exceto os de número primo também seria “100%”, mas um pouco pior que o 100% anterior, pois a densidade dos primos entre 1 e N é aproximadamente , para N grande, enquanto a densidade dos quadrados é . Tente apenas fazer o melhor que vc puder.)