Ask The Wizard #369

=(log(1+SQRT(5))-log(2))/(log(4)-log(3)) =~ 1.67272093446233.

6,210,001,000

The maximum probability of success is approximately 31.18278207%

The general idea is if at least one prisoners fail, then lots of them may as well fail, as the ultimate outcome of death for everyone is still the same. So, a good strategy would maximize the probability of everybody's success at the expense of a high probability of many failures as well.

Consider a strategy where the player opens any box. He then reads the number on the paper in it and then opens that box second. He then reads the paper in that second box and opens the box with that number third. If he keeps repeaing this process, he will eventually be lead back to the box he started with.

If the player follows this strategy and his own number is somewhere in that loop of numbers, then he will obviously eventually find, assuming no limit on boxes he may open.

To ensure the player always eventually finds his number, he can start with his own number. That way, he will eventually come back to it, although it could take anywhere from 1 to 100 box openings.

A set of boxes where this strategy eventually leads back to the first box is called a closed loop. The number of boxes in a closed loop is the size of the loop.

The key to this problem is every prisoner will be successful if there is no closed loop greater than size 50.

If there is a closed loop of 100, the prisoners will fail. What is that probability? There is a 99/100 probability the first box does NOT lead to itself. If it doesn't lead to itself, there is a 98/99 probability the second box does not lead to the original number. If that box doesn't lead to itself, then there is a 97/98 probability the next box does not lead to itself. Extending this logic, there is a (99/100)*(98/99)*(97/88)*...*(3/4)*(2/3)*(1/2) = 1/100 probability there is a closed loop of size 100.

What about a closed loop of 99? With a closed loop of 99, there would be another closed loop of 1. That closed loop of one could be any of the 100 boxes. For any one box, there is a 1/100 chance it leads to itself. For the other 99, there is a 1/99 chance they form a closed loop, by the logic above for a closed loop of 100. So, the probability of a closed loop of 99 is 100 × (1/100) & (1/99) = 1/99.

What about a closed loop of 98? With a closed loop of 98, there would be another two boxes that would lead to each other somebody, either two closed loops of one or one closed loop of two. That closed loop of one could be any of the 100 boxes. For any one box, there is a 1/100 chance it leads to itself. For the other 99, there is a 1/99 chance they form a closed loop, by the logic above for a closed loop of 100. So, the probability of a closed loop of 99 is 100 × (1/100) & (1/99) = 1/99.

What about a closed loop of 98? With a closed loop of 98, there would be another two boxes that would lead to each other somebody, either two closed loops of one or one closed loop of two. There are combin(100,2)=4,950 ways to choose two boxes out of 100. Once two are chosen, the probability those two boxes have the papers inside matching their box numbers, in any configuration, is (2/100)*(1/99) = 1 in 4,950. Then the probability the other 98 form a closed loop is 1/98. So, the probability of a closed loop of 98 is (4950)*(1/4950)*(1/98) = 1/98.

We can keep following this logic down to a closed loop of 51 having a probability of 1/51.

The probability of failure is pr(closed loop of 100) + pr(closed loop of 99) + pr(closed loop of 98) + ... + pr(closed loop of 51) = 1/100 + 1/99 + 1/98 + 1/97 + ... + 1/51 =~ 0.6881721793.

If the probability of failure is 0.688172179, then probability of success is 1 - 0.6881721793 =~ 0.3118278207.

(1/1) + (1/2) + (1/3) + ... + (1/100) =~ 5.187377518.

Suppose there is just one employee who comes to the Secret Santa party. Obviously he will pick himself, so one closed loop.

Then a second employee arrives late and asks to join. They give her a list of the now two employees. There is a 1/2 chance she picks employee 1 and 1/2 herself. If she picks employee 1, then she can be squeezed into his loop, where she buys for employee 1 and he buys for her. So, now we're at 1 + 0.5*1 = 1.5

Then a third employee arrives late and asks to join. They give her a list of the now 3 employees. There is a 2/3 chance she picks employee 1 or 2 and 1/3 herself. If she picks employee 1 or 2, then she can be squeezed into their loop, where she buys for employee she picks and the one who formally was supposed to buy for that employee now buys for 3. So, now we're at 1.5 + (1/3) = 11/6.

Then a fourth employee arrives late and asks to join. They give her a list of the now 4 employees. There is a 3/4 chance she picks employee 1 to 3 and 1/4 herself. If she picks employee 1 to 3, then she can be squeezed into their loop, where she buys for employee she picks and the one who formally was supposed to buy for that employee now buys for 4. So, now we're at 11/6 + (1/4) = 25/12.

Keep doing this and the final answer is 1/1 + 1/2 + 1/3 + ... + 1/100 =~ 5.187377518.