C#
100 Prisoners
7/22/2022: About a month ago I was watching a youtube video from Veritasium¹, where he explains how loops allow us to increase the chances of finding an object in a system by an exponential amount, he does this by using a riddle. The riddle is the following:
There are 100 boxes in a room, each box is numbered, and it contains a random number within it, there are 100 Prisoners, each prisoner needs to go into the room and find their own number (prisoner 1 needs to find a box containing the number one inside), each prisioner has up to 50 boxes they can open, if just a single one of the prisoners cannot find their number within 50 boxes, all 100 prisoners will die.
In the video he explains there is a 8*10^(-31)% chance that each prisoner will find their number inside a box, (that is an 8 after 30 zeroes) this is because each prisoner has a 50% chance to find their number, so 100 prisoners in a row finding their number with a 50% chance each time is extremely low, however, by following the 'loop' the video claims that every single prisoner is able to find their number inside a box within 50 tries by almost a total 1/3 of the time, 30.7% to be exact.
The method he gives is very simple, prisoner number 1 opens a random box, lets say #35, within the box there is the number 75, prisoner 1 should go to box #75 and open it, etc. In summary, the prisoner should go to the box with the same number that the prisoner found inside the first box, and do this over and over until they find their number inside one of the boxes. When the prisoner finds their number, they must put everything back together in the same way they found it, and leave, this process is repeated by each prisoner until they all pass, or they all die (this counts as one round). Each round should have a completly new random set of box numbers as well as numbers within those boxes.
Halfway trough the video I decided to test it myself, I built this little program in a little more time than I would like to admit (about an hour), the main culprit behind the lengthiness of creating the program was forgetting to reset the '50 maximum boxes opened' counter back to 0 after each prisoner found their number. After a good amount of debugging I found my mistake, fixed it and gave it a go:
While the video claims the prisoners have a 30.7% chance, the closest I got was 31.19%. As the image below shows, this was after 1 million rounds. In the video they use calculus to find the answer, by taking an integral of the probability of success. Of course their calculation is a lot more accurate, as it takes into account an infinite number of rounds, but I think that getting within 1.6% of the real answer using a 'real life' approach is not bad at all!.
The code I created:
