O problema dos 100 prisioneiros
Uma penitenciária tem 100 prisioneiros, e o diretor propõe um jogo: em uma sala há cem caixas com tampas numeradas de 1 a 100. Dentro de cada caixa há um papel contendo o número de identificação de um dos prisioneiros, de 1 a 100, distribuídos aleatoriamente (sem repetições). Um por vez, cada prisioneiro pode entrar na sala e abrir até 50 caixas, tentando encontrar o papel com seu próprio número. As caixas são fechadas após cada tentativa, e os prisioneiros não podem se comunicar entre si durante o processo. Se todos encontrarem seus próprios números, todos serão libertados; se qualquer um deles falhar, todos permanecem presos. Ao ler esse problema, a primeira impressão é de que a chance de liberdade dos prisioneiros não é nada boa. Cada prisioneiro tem uma chance de 50% de encontrar seu próprio número abrindo as caixas aleatoriamente, e a probabilidade de que todos encontrem seus respectivos números é, portanto, de (1/2)100. Um prisioneiro que faça essa conta desanimará ao perceber que tem uma chance em 1030, que é equivalente a ganhar na Mega-Sena quatro vezes seguidas! Mas esse problema só é digno da atenção do leitor porque existe uma estratégia que os prisioneiros podem combinar antes de iniciar o jogo, aumentando impressionantemente as suas chances de liberdade para mais de 30%. Caso ainda não conheça esse problema, esse é o momento para interromper a leitura e pensar por algum tempo em qual é essa estratégia aparentemente milagrosa. Em vez de abrir 50 caixas aleatórias, cada prisioneiro deve começar abrindo a caixa com o seu próprio número — por exemplo, o prisioneiro 23 abre a caixa 23. Se nela estiver o número 23, ele teve sorte e termina sua vez com sucesso. Caso contrário, ele encontra o número de outro prisioneiro, digamos 41, e então abre a caixa 41 na próxima tentativa. Ele repete esse processo, sempre abrindo a caixa cujo número acabou de encontrar, até no máximo 50 tentativas. Primeiramente, é importante notar que, ao utilizar essa estratégia, cada caixa passa a fazer parte de um único ciclo fechado. O ciclo mais curto possível contém apenas uma caixa, que aponta para o próprio número, enquanto o mais longo envolve todas as 100 caixas. De maneira geral, um arranjo aleatório dos números nas caixas resulta em vários ciclos de diferentes tamanhos. Para que todos os prisioneiros encontrem seus próprios números seguindo a estratégia descrita, basta que nenhum desses ciclos tenha mais do que 50 caixas [1]. O problema então se resume a calcular a probabilidade de que nenhum ciclo tenha comprimento maior do que 50. Os detalhes matemáticos serão poupados aqui, mas esse cálculo resulta na probabilidade de 31% de sucesso para os prisioneiros [1, 2]. Esse problema foi originalmente proposto em 2003 pelo cientista da computação dinamarquês Peter Bro Miltersen, com o objetivo de ilustrar conceitos da computação, especialmente na área da complexidade de comunicação [3]. Mesmo conhecendo a estratégia vencedora, o resultado continua surpreendente. Trata-se de mais um exemplo em que a matemática desafia a intuição, revelando justamente o que a torna tão fascinante. Autor: Angelo Zanona Neto
Referências: [1] Veritasium. The Riddle That Seems Impossible Even If You Know The Answer. YouTube, 2022. https://youtu.be/iSNsgj1OCLA?si=bdnhrfeModtRoLn3. Acessado em 11 de julho de 2025. [2] Duarte, P. M. N. R. D. Problema dos Cem. Disponível em: https://webpages.ciencias.ulisboa.pt/~pmduarte/Problems/prision_2.pdf. Acessado em 11 de julho de 2025. [3] Gál, A., Miltersen, P. B. The Cell Probe Complexity of Succinct Data Structures. BRICS Report Series, 2003. Disponível em: https://www.brics.dk/RS/03/44/BRICS-RS-03-44.pdf. Acessado em 16 de julho de 2025. [4] (Imagem) Enigma: Salve-se quem puder. Hypercubic: um hyperespaço de ideias, 2013. Disponível em: https://www.blogs.unicamp.br/hypercubic/2013/04/enigma-salve-se-quem-puder/. Acessado em 11 de julho de 2025.
