Pergunte ao Mago #369

A ideia geral é que, se pelo menos um prisioneiro falhar, muitos outros também podem falhar, já que o resultado final da morte para todos continua o mesmo. Portanto, uma boa estratégia maximizaria a probabilidade de sucesso de todos, mesmo que isso significasse uma alta probabilidade de muitas falhas.

Considere uma estratégia em que o jogador abre qualquer caixa. Ele lê o número no papel que está dentro dela e abre essa caixa em seguida. Depois, lê o papel na segunda caixa e abre a caixa com o mesmo número em seguida. Se ele continuar repetindo esse processo, eventualmente retornará à caixa inicial.

Se o jogador seguir essa estratégia e o seu número estiver em algum lugar nesse ciclo de números, então ele obviamente acabará encontrando a resposta, assumindo que não haja limite para o número de caixas que ele pode abrir.

Para garantir que o jogador sempre encontre seu número, ele pode começar com o próprio número. Dessa forma, ele acabará voltando a ele, embora isso possa levar de 1 a 100 aberturas de caixas.

Um conjunto de caixas onde essa estratégia eventualmente leva de volta à primeira caixa é chamado de circuito fechado. O número de caixas em um circuito fechado é o tamanho do circuito.

A chave para este problema é que todos os prisioneiros terão sucesso se não houver nenhum circuito fechado com tamanho superior a 50.

Se houver um ciclo fechado de 100, os prisioneiros falharão. Qual é essa probabilidade? Há 99% de probabilidade de que a primeira caixa NÃO leve a si mesma. Se ela não levar a si mesma, há 98% de probabilidade de que a segunda caixa não leve ao número original. Se essa caixa não levar a si mesma, então há 97% de probabilidade de que a próxima caixa não leve a si mesma. Estendendo essa lógica, há (99% de probabilidade)*(98% de probabilidade)*(97% de probabilidade)*(3% de probabilidade)*(2% de probabilidade)*(1/2) = 1/100 de que haja um ciclo fechado de tamanho 100.

E quanto a um circuito fechado de 99? Com um circuito fechado de 99, haveria outro circuito fechado de 1. Esse circuito fechado de 1 poderia ser qualquer uma das 100 caixas. Para qualquer caixa, há 1/100 de chance de ela levar a si mesma. Para as outras 99, há 1/99 de chance de elas formarem um circuito fechado, pela lógica acima para um circuito fechado de 100. Portanto, a probabilidade de um circuito fechado de 99 é 100 × (1/100) e (1/99) = 1/99.

E quanto a um circuito fechado de 98? Com um circuito fechado de 98, haveria mais duas caixas que se conectariam de alguma forma, seja formando dois circuitos fechados de uma caixa ou um circuito fechado de duas caixas. Esse circuito fechado de uma caixa poderia ser qualquer uma das 100 caixas. Para qualquer caixa individual, há 1/100 de chance de que ela se conecte a si mesma. Para as outras 99 caixas, há 1/99 de chance de que elas formem um circuito fechado, seguindo a lógica acima para um circuito fechado de 100. Portanto, a probabilidade de um circuito fechado de 99 caixas é 100 × (1/100) × (1/99) = 1/99.

E quanto a um circuito fechado de 98? Com um circuito fechado de 98, haveria outras duas caixas que se conectariam de alguma forma, seja formando dois circuitos fechados de um único elemento ou um circuito fechado de dois elementos. Existem combin(100,2) = 4.950 maneiras de escolher duas caixas dentre 100. Uma vez escolhidas duas, a probabilidade de que os papéis dentro dessas duas caixas correspondam aos seus respectivos números, em qualquer configuração, é (2/100) * (1/99) = 1 em 4.950. Então, a probabilidade de que as outras 98 formem um circuito fechado é 1/98. Portanto, a probabilidade de um circuito fechado de 98 é (4.950) * (1/4.950) * (1/98) = 1/98.

Podemos continuar seguindo essa lógica até um ciclo fechado de 51 com probabilidade de 1/51.

A probabilidade de falha é pr(circuito fechado de 100) + pr(circuito fechado de 99) + pr(circuito fechado de 98) + ... + pr(circuito fechado de 51) = 1/100 + 1/99 + 1/98 + 1/97 + ... + 1/51 ≈ 0,6881721793.

Se a probabilidade de falha for 0,688172179, então a probabilidade de sucesso será 1 - 0,6881721793 ≈ 0,3118278207.

Suponha que haja apenas um funcionário que compareça à festa do Amigo Secreto. Obviamente, ele escolherá a si mesmo, fechando assim o ciclo.

Então, uma segunda funcionária chega atrasada e pede para participar. Entregam a ela uma lista com os nomes dos dois funcionários. Há 50% de chance de ela escolher o funcionário 1 e 50% de chance de escolher a si mesma. Se ela escolher o funcionário 1, ela pode ser incluída no esquema dele, onde ela compra para o funcionário 1 e ele compra para ela. Então, agora estamos com 1 + 0,5 * 1 = 1,5.

Então, uma terceira funcionária chega atrasada e pede para participar. Entregam a ela uma lista com os nomes dos três funcionários. Há 2/3 de chance de ela escolher o funcionário 1 ou 2 e 1/3 de chance de escolher a si mesma. Se ela escolher o funcionário 1 ou 2, ela pode ser incluída no esquema, onde ela compra para o funcionário que escolheu e quem deveria comprar para esse funcionário agora compra para o terceiro. Então, agora estamos com 1,5 + (1/3) = 11/6.

Então, uma quarta funcionária chega atrasada e pede para participar. Entregam a ela uma lista com os nomes dos quatro funcionários. Há 3/4 de chance de ela escolher os funcionários de 1 a 3 e 1/4 de chance de escolher a si mesma. Se ela escolher os funcionários de 1 a 3, então ela pode ser incluída no esquema, onde ela compra para o funcionário que escolheu e quem antes deveria comprar para esse funcionário agora compra para o quarto. Então, agora estamos com 11/6 + (1/4) = 25/12.

Continue fazendo isso e a resposta final será 1/1 + 1/2 + 1/3 + ... + 1/100 =~ 5,187377518.