100 Labelled Boxes
As so often happens with this genre of puzzle, we are going to frame it as a situation involving prisoners. In a prison there are 100 inmates all wearing a distinct shirt labelled from 1 to 100. They are led one by one into a room containing 100 boxes in a row, numbered from 1 to 100 (in a Deal or No Deal way).
Inside each box is the number of an inmate, 1 through 100 again, although the number inside the box doesn't necessarily correspond with the number on the outside of the box.
When prisoner number 1 enters the room they may open up a box and check inside. The goal is to find the number corresponding with your shirt. In total the prisoner is allowed to check 50 of the 100 boxes. If they are successful in their attempt then all of the boxes are closed again and it is prisoner number 2's turn. If all 100 prisoners manage to find their number within the 50 tries (each) then everyone gets released from the prison.
However, if a single prisoner doesn't manage to find their number then everyone is executed. What is a good strategy?
Well it looks pretty bleak to start with. Prisoner number 1 appears to have only a half chance of getting their number within 50 attempts, as will each subsequent prisoner. So the total probability of everyone getting it right is (1/2)^100 which is about 10^-31. This is the sort of thing that happens when you turn on the Infinite Probability Drive.
However, there is a clever strategy which abuses some quite sophisticated mathematics and amazingly manages to bump the probability of winning to slightly over 31%. The procedure for each prisoner is as follows:
1. Open the box which bares your number on it.
2. Look inside and go to whichever box matches the number you have just revealed.
3. Repeat step 2 until you have opened 50 boxes.
For example Prisoner number 1 opens box 1 and finds the number 37. He then opens box 37 and finds the number 15. This continues until the prisoner eventually opens up a box to reveal the number 1.
Sometimes the boxes will loop and this is the key to understanding the mathematics. For example maybe 1 -> 37 -> 15 -> 1 again. This will make Prisoners 1, 37 and 15 find their numbers within 3 steps each. These loops are a good thing.
Some loops may be length of only 1 if the prisoner's number is in the first box, or they may be far longer. If there is a single loop of length 51 or greater (and there can only be one) then all of the prisoners within that loop will be unable to find their number in the required number of attempts and everyone will fail. So the question becomes: how likely is it to get a loop of 51 or bigger for 100 numbers.
Aside: A couple of years ago I went on holiday with 6 other people and we played a game called assassin. You were given the name of one of the other people in the group, a location and an object at random. If you could convince that person to pick up that object under their own free will in that location then you had "killed" them. Once you did that you inherited their target. The whole game was last person standing. As an example, I had to "kill" a particular person in a car by getting them to hold an egg. I was not successful, but my own killer who killed me with a dog in a different car managed it. I thoroughly recommend this game if you want a weekend of everyone point blank refusing to pick up anything.
A question arose as to whether we were necessarily a loop of 7 people, or whether there were smaller sub loops. How likely was a loop of 7? We knew there were no loops of 1 because if you drew your own name in the hat you put it back and picked again.
The answer to this I can't remember, but you can brute force it. However I started working on the much more general problem of n people and the maths got massively case based. I forgot about the problem for a few years until I heard of this prisoner puzzle and realised that it had exactly the same form. Crucially, in solving it mathematicians had developed exactly the correct sophisticated tools for solving my assassin problem. For the 100 prisoner problem the probability of getting a loop of more than 50 is 1/51+1/52+...+1/100. By taking 1 minus this and evaluating it works out at about 0.31183 or 31.183%.
Notice that if we increased this to 1000 prisoners then it doesn't decrease the odds of success drastically. 1-(1/501+1/502+...+1/1000)=0.30735 or 30.735%. This means that we have a solution which scales well as we increase the number of prisoners n and in fact the limit tends to 30.685% as n tends to infinity.
