To run the experiment, run ruby experiment.rb. You can adjust the parameters of the experiment at very bottom of experiment.rb (the default runs the experiment 1000 times with 100 boxes).
Let's say we have 100 prisoners, each numbered 1 to 100.
| 1🧍 | 2🧍 | 3🧍 | 4🧍 | 5🧍 | 6🧍 | 7🧍 | 8🧍 | 9🧍 | 10🧍 |
| 11🧍 | 12🧍 | 13🧍 | 14🧍 | 15🧍 | 16🧍 | 17🧍 | 18🧍 | 19🧍 | 20🧍 |
| 21🧍 | 22🧍 | 23🧍 | 24🧍 | 25🧍 | 26🧍 | 27🧍 | 28🧍 | 29🧍 | 30🧍 |
| 31🧍 | 32🧍 | 33🧍 | 34🧍 | 35🧍 | 36🧍 | 37🧍 | 38🧍 | 39🧍 | 40🧍 |
| 41🧍 | 42🧍 | 43🧍 | 44🧍 | 45🧍 | 46🧍 | 47🧍 | 48🧍 | 49🧍 | 50🧍 |
| 51🧍 | 52🧍 | 53🧍 | 54🧍 | 55🧍 | 56🧍 | 57🧍 | 58🧍 | 59🧍 | 60🧍 |
| 61🧍 | 62🧍 | 63🧍 | 64🧍 | 65🧍 | 66🧍 | 67🧍 | 68🧍 | 69🧍 | 70🧍 |
| 71🧍 | 72🧍 | 73🧍 | 74🧍 | 75🧍 | 76🧍 | 77🧍 | 78🧍 | 79🧍 | 80🧍 |
| 81🧍 | 82🧍 | 83🧍 | 84🧍 | 85🧍 | 86🧍 | 87🧍 | 88🧍 | 89🧍 | 90🧍 |
| 91🧍 | 92🧍 | 93🧍 | 94🧍 | 95🧍 | 96🧍 | 97🧍 | 98🧍 | 99🧍 | 100🧍 |
In addition, there is a room with 100 boxes, labeled 1 to 100.
| 1📦 | 2📦 | 3📦 | 4📦 | 5📦 | 6📦 | 7📦 | 8📦 | 9📦 | 10📦 |
| 11📦 | 12📦 | 13📦 | 14📦 | 15📦 | 16📦 | 17📦 | 18📦 | 19📦 | 20📦 |
| 21📦 | 22📦 | 23📦 | 24📦 | 25📦 | 26📦 | 27📦 | 28📦 | 29📦 | 30📦 |
| 31📦 | 32📦 | 33📦 | 34📦 | 35📦 | 36📦 | 37📦 | 38📦 | 39📦 | 40📦 |
| 41📦 | 42📦 | 43📦 | 44📦 | 45📦 | 46📦 | 47📦 | 48📦 | 49📦 | 50📦 |
| 51📦 | 52📦 | 53📦 | 54📦 | 55📦 | 56📦 | 57📦 | 58📦 | 59📦 | 60📦 |
| 61📦 | 62📦 | 63📦 | 64📦 | 65📦 | 66📦 | 67📦 | 68📦 | 69📦 | 70📦 |
| 71📦 | 72📦 | 73📦 | 74📦 | 75📦 | 76📦 | 77📦 | 78📦 | 79📦 | 80📦 |
| 81📦 | 82📦 | 83📦 | 84📦 | 85📦 | 86📦 | 87📦 | 88📦 | 89📦 | 90📦 |
| 91📦 | 92📦 | 93📦 | 94📦 | 95📦 | 96📦 | 97📦 | 98📦 | 99📦 | 100📦 |
Inside each box is a note with a random number in it, 1 to 100.
| 1 📦 (34) | 2 📦 (79) | 3 📦 (25) | 4 📦 (82) | 5 📦 (83) | 6 📦 (38) | 7 📦 (69) | 8 📦 (87) | 9 📦 (47) | 10 📦 (81) |
| 11 📦 (31) | 12 📦 (3) | 13 📦 (50) | 14 📦 (18) | 15 📦 (52) | 16 📦 (9) | 17 📦 (27) | 18 📦 (63) | 19 📦 (32) | 20 📦 (6) |
| 21 📦 (55) | 22 📦 (30) | 23 📦 (45) | 24 📦 (4) | 25 📦 (37) | 26 📦 (36) | 27 📦 (96) | 28 📦 (7) | 29 📦 (5) | 30 📦 (57) |
| 31 📦 (75) | 32 📦 (13) | 33 📦 (72) | 34 📦 (91) | 35 📦 (53) | 36 📦 (8) | 37 📦 (56) | 38 📦 (22) | 39 📦 (24) | 40 📦 (74) |
| 41 📦 (21) | 42 📦 (51) | 43 📦 (92) | 44 📦 (90) | 45 📦 (16) | 46 📦 (23) | 47 📦 (93) | 48 📦 (11) | 49 📦 (86) | 50 📦 (68) |
| 51 📦 (43) | 52 📦 (42) | 53 📦 (40) | 54 📦 (19) | 55 📦 (64) | 56 📦 (99) | 57 📦 (89) | 58 📦 (17) | 59 📦 (26) | 60 📦 (15) |
| 61 📦 (20) | 62 📦 (100) | 63 📦 (49) | 64 📦 (14) | 65 📦 (41) | 66 📦 (48) | 67 📦 (98) | 68 📦 (77) | 69 📦 (10) | 70 📦 (60) |
| 71 📦 (54) | 72 📦 (78) | 73 📦 (61) | 74 📦 (94) | 75 📦 (1) | 76 📦 (62) | 77 📦 (65) | 78 📦 (67) | 79 📦 (76) | 80 📦 (44) |
| 81 📦 (2) | 82 📦 (85) | 83 📦 (84) | 84 📦 (88) | 85 📦 (71) | 86 📦 (46) | 87 📦 (28) | 88 📦 (39) | 89 📦 (73) | 90 📦 (29) |
| 91 📦 (33) | 92 📦 (35) | 93 📦 (80) | 94 📦 (58) | 95 📦 (59) | 96 📦 (12) | 97 📦 (66) | 98 📦 (95) | 99 📦 (97) | 100 📦 (70) |
The warden of the prison has made a deal with the 100 prisoners. They may converse with each other as long as they like to make a plan. Then they will one-by-one enter the room with the 100 boxes.
Each prisoner may open 50 boxes. If a prisoner opens a box with their Prisoner Number inside, they "succeed". Either way, they then leave the room through another door, all boxes are closed, and the next prisoner takes his turn. After the last prisoner, if every prisoner has succeeded at finding their box, they all go free. Otherwise they are all executed.
They may not mark the boxes. No one can see what the previous prisoner has looked at. They cannot communicate with one another at all once they have entered the room of boxes.
If every prisoner opens 50 boxes randomly, they each have a 50% chance of succeeding. Hence, for 100 prisoners, there is a 0.5100 chance of all of them going free. That is a very very small chance, 1 in one nonillion (1,267,650,600,228,229,401,496,703,205,376). For scale, there are about 7.5 sextillion grains of sand on Earth.
So picture needing to select the correct grain of sand out of all of the sand on the planet, but 1 billion times less likely. They're all going to die.
In addition if they don't strategize at all, that probability actually decreases. For example if 51 prisoners pick boxes 1-50, their chances of them going free are reduced to zero since at least 1 of the 51 will not have a box in boxes 1-50.
Is there a way to improve their chances? Believe it or not, there is a simple way to increase their probablity dramatically. Very dramatically. By a factor of hundreds of octillions. In fact, if they use the right strategy, their probabilty of going free increases to 31%.
Sounds unbelieveable right? Here's the strategy:
Prisoner #1 picks Box #1. If it doesn't have a 1 inside of it (say it has #34, like our example above). Prisoner #1 will pick Box #34 next. If Box #34 doesn't have a 1 inside of it (say it has 91), Prisoner #1 will pick Box #91 next. Prisoner #1 continues until either he finds the box with a 1 inside of it, or he's opened 50 boxes and everyone dies.
Prisoner #2 picks Box #2 and follows the same pattern (checking Box #72, #78, ...). And so on with all of the prisoners. If every prisoner does this, they have a 31% chance of surviving. That's absurd. Why does this improve the probability?
The simple answer is: It divides the 100 boxes into "loops". For example, Prisoner #10 will find their box in this order:
10 → 90 → 80 → 28 → 32 → 62
Prisoner #90 will be in the same loop: 90 → 80 → 28 → 32 → 62 → 10
Boxes #80, #28, #32, and #32 will be in the same loop. It will take all of them 6 boxes to find the box with their number in it.
So if all "loops" happen to be shorter than 51 boxes, then all prisoners will go free. But what is the probability of that? I'll spare you the math, but it's apparently around 31%
That's what this app is going to find out! Let's simulate this very experiment, and see how often the prisoners are set free!
I'm sure there's a quick and codey way to solve this problem, but I'm deciding to do a class-based solution, with metaphorical naming principles.
A Box has both a Label (the number on the Box) and a Value (what's inside the Box).
Value is stored directly on the Box, while Label is the index of the Box in the list of Boxes.
The Room has n Boxes in it (100 for this specific problem). When the Room initializes, it creates 100 Boxes and assigns them a Label and Value, ensuring that no numbers are repeated.
Since it stores the Boxes as an array (list), I just used the index of the Box in the array as a Label. Makes it run much faster.
A Prisoner has a Number, which is the number that they are trying to find in a Box.
The Experiment covers everything. It's where the Room exists, with Boxes inside of them, and also where the Prisoners live.
When created, the Experiment generates 100 Prisoners as well as a Room (which comes with 100 Boxes). When run is called, the Experiment sends each Prisoner into the Room to open Boxes using the above strategy. It records how many Boxes the Prisoner had to open to find their number.
If any Prisoner has to check more than 50 Boxes to find their number, then the Prisoners fail to be freed from the prison. If all of them get to their Box by opening 50 or fewer Boxes, they succeed.
Experiment can be run many times, using as many Boxes as desired. Experiment.run_n_times(num_times, num_boxes) will return the success rate of the Prisoners after that many runs.
When I ran the Experiment 1,000 times with 100 Boxes, sure enough the success rate of the Prisoners was 30.56%. Looks like they were a bit unlucky. After increasing to 1,000,000 Experiments, they had a success rate of 31.18, closer to the average.
So yes, this solution is correct. Using the "loop" strategy, prisoners have a 31% chance of surviving. I'm still having a hard time wrapping my head around that.
Something very fun to think about: I increased the number of Prisoners (and therefore Boxes) to 1,000,000, and the Prisoners STILL survived 30.7% of the time using the strategy. Compared to the 21,000,000 chance they had of surviving otherwise (not even going to try to display that number).
Work in progress! I'm sure there's a solution online, but I'm still trying to figure it out on my own.