Vincent_van_Gogh

Vincent Van Gogh, ‘La ronde des prisonniers’, 1890

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.


0 comentário

Igor Santos · 1 de abril de 2013 às 20:30

Uma dúvida: eles não devem mudar o arranjo das caixas, mas podem tocar nelas?

    Renato Pincelli · 1 de abril de 2013 às 20:38

    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 · 1 de abril de 2013 às 20:53

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 · 1 de abril de 2013 às 21:04

    Não. E não.

    rafinha.bianchin · 2 de abril de 2013 às 11:06

    Hmm, eles podem ver os outros abrindo as caixas?

    Renato Pincelli · 2 de abril de 2013 às 12:08

    Não. Como já foi dito no texto, vai um de cada vez, sob vigilância dos guardas.

rafinha.bianchin · 2 de abril de 2013 às 20:53

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.

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *