O enigma dos prisioneiros em que cada um precisa descobrir seu nome na caixa ou todo mundo morre é um dos mais difíceis que já publicamos. Apenas dois comentaristas se manifestaram, mas houve mais comentários tirando dúvidas do enunciado do que soluções. Aliás, apenas uma solução foi arriscada. A seguir, apresentamos a solução oficial e a única resposta que recebemos.
Solução Oficial
Este enigma foi encontrado no paper Seven Puzzles You Think You Must Not Have Heard Correctly, with solutions, de Peter Winkler, Professor de Matemática e Ciência da Computação do Darthmouth College. Esse artigo foi posteriormente adicionado como apêndice ao volume II de Mathematical Puzzles: A Connoisseur’s Collection (A K Peters, 2004), do mesmo autor. Eis a solução apresentada por Winkler:
Para resolver o problema, os prisioneiros precisam, primeiro, decidir pela nomeação aleatória das caixas com seus próprios nomes. O motivo para fazer a divisão aleatoriamente é que isso torna impossível para os carcereiros distribuir seus nomes pelas caixas de modo a sabotar o plano. Quando for levado ao ginásio, cada prisioneiro inspeciona sua própria caixa (i.e., a caixa que, por convenção, foi associada ao seu nome). Ele vai descobrir um nome e depois procura pela caixa daquele nome e então vai para a caixa do nome encontrado na segunda caixa e assim por diante, até que ele encontre seu próprio nome ou abra 50 caixas.
Esta parece ser uma estratégia. Mas será que ela funciona? Bem, o processo que associa a um dono de caixa o nome encontrado em sua caixa é uma permutação dos 100 nomes, escolhidos de forma uniformemente randômica do conjunto de todas as possíveis permutações. Ao procurar por seu nome, cada prisioneiro está seguindo um ciclo da permutação, que começa com a sua caixa e (se ele não passar do limite de 50) termina com um pedaço de papel com seu próprio nome. Se a permutação não tiver ciclos de comprimento maior que 50, este processo sempre vai funcionar e os prisioneiros acabam sãos e salvos.
De fato, a probabilidade de que uma permutação uniformemente randômica dos números de 1 a 2nnão tenha um comprimento de ciclo maior que n é de pelo menos 1 menos logaritmo natural de 2 — aproximadamente 30,6853%.
Para perceber isso, considere k > n e conte as permutações que tem um ciclo C de comprimento exatamente igual a k. Há
modos de selecionar as entradas em C, (k-1)! modos de ordená-las e (2n-k)! modos de permutar o resto. O produto desses números é (2n)!/k. Uma vez que no máximo um k-ciclo pode existir numa dada permutação, a probabilidade de que haja um é exatamente 1/k. Segue-se que a probabilidade de que não haja um ciclo mais longo é:
onde Hm é a soma das recíprocas dos primeiros m inteiros positivos, ou aproximadamente ln m. Assim, nossa probabilidade é de cerca de 1 – ln 2n + ln n = 1 – ln 2 (e na verdade é sempre um pouco maior). Para n = 50, nós conseguimos que a probabilidade de sobrevivência dos prisioneiros seja de 31.1827821%.
Winkler afirma que esse problema foi originalmente proposto, ainda que de maneira mais complexa, por Peter Bro Miltersen, em um artigo em co-autoria com Anna Gal (a referência, citada em nota de rodapé, é apenas “The cell probe complexity of succint data structures, ICALP, 2003″). Ainda segundo Winkler, Eugene Curtain e Max Weshauer teriam provado que tal solução não pode ser melhorada.
Solução do leitor
No singular mesmo, pois o único a apresentar algo que se pode considerar uma solução possível (ainda que me pareça incorreta), foi o rafinha.bianchin:
Como já disse antes, o método para que os detentos saibam quais caixas já foram abertas é deixando as caixas com o nome do detento visitante com a tampa aberta, logo, após cada visita, existe uma caixa a menos para escolher.
Vamos chamar de W o número de maneiras possíveis para que se escolha 50 caixas dentre 100. Logo, W=100!/(50!*50!). Pelo método da tentativa e erro (mas não é muito complicado entender o porquê) descobri que, se ele tem W meios de escolher, logo ele tem W/2 meios de que a caixa com seu nome seja aberta. O próximo W é de 99!/(50!*49!), e assim por diante. Temos, portanto, que W = N!/[50!*(N-50)!]. No caso, não deveremos dividir por dois, e sim por (99/50).
Para o primeiro detento, a chance de que ele descubra a caixa com seu nome é bastante pequena, mas, após cada visita, a probabilidade de acerto vai crescendo.
Aqui, o rafinha propõe outra maneira de identificar as caixas: deixar as tampas abertas. É uma possibilidade, mas não me parece muito inteligente. Quem garante que os guardas não tampam as caixas após cada passagem? A não ser que o rafinha tenha encontrado uma solução muito simplificada, a parte matemática também não me parece adequada. A única coisa correta é a conclusão: as chances de sucesso são pequenas a princípio, mas crescem a cada passagem. No entanto, a solução original indica que esse crescimento não é indefinido (mesmo porque trata-se de passagens limitadas por um número limitado de caixas).
