A penitenciária está lotada e o diretor não sabe mais o que fazer. Incapaz de decidir quem deve soltar ou quem deve ser morto, o diretor propõe uma saída matemática. Os nomes de 100 prisioneiros são colocados em um pedaço de papel e guardados dentro de 100 caixas de madeira (um nome em cada caixa). E as caixas, por sua vez, são postas no ginásio da prisão. “Um por um”, explica o diretor, durante o anúncio do esquema, “os prisioneiros serão levados ao ginásio pelos guardas. À procura de seu nome, cada um pode olhar no máximo 50 caixas, mas deve sair sem mudar o modo como elas estão arranjadas. Depois da saída do ginásio, fica proibida a comunicação entre os detentos.”
Os prisioneiros percebem que há uma brecha nas regras, que lhes dá a chance de criar uma estratégia para facilitar as buscas. E eles vão mesmo precisar se entender, já que cada prisioneiro deverá encontrar seu próprio nome. Se isso não acontecer, todos eles serão executados.
Assim, como evitar que todo mundo procure nas mesmas caixas?
- Nível: de médio para difícil. A lógica é simples até, mas a matemática para comprová-la é mais complicada.
- Dica: se cada prisioneiro examinar um conjunto aleatório de 50 caixas, a probabilidade de sobrevivência dos condenados é de míseros 1/2^100 ≈ 0,0000000000000000000000000000008. É claro que o resultado poderia ser pior, especialmente se todos eles olharem para as mesmas 50 caixas — nesse caso, as chances caem a zero. Entretanto, é possível elevar a probabilidade de sobrevivência para aproximadamente 30%.
- Solução: será publicada, assim que me for possível, na sexta, 05/04.
-
UPDATE (04/04, 20H05): Eu não devia, mas vou lhes ajudar. Considerando a dificuldade deste enigma, as poucas manifestações e que, por motivos pessoais, não me será possível publicar a resposta na sexta-feita (amanhã), decreto que a resposta e a discusão dos comentários será feita no domingo, 07/04.
Igor Santos
Uma dúvida: eles não devem mudar o arranjo das caixas, mas podem tocar nelas?
Renato Pincelli
Sim, podem tocar nelas. Até porque eles precisam abri-las. E lembrem-se: cada um só pode abrir, no máximo, 50 caixas.
Igor Santos
Eles sabem a ordem em que estão sendo liderados ao pátio? E, finalmente, eles sabem o momento em que o último voltou?
Renato Pincelli
Não. E não.
rafinha.bianchin
Hmm, eles podem ver os outros abrindo as caixas?
Renato Pincelli
Não. Como já foi dito no texto, vai um de cada vez, sob vigilância dos guardas.
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.