Summary of The Riddle That Seems Impossible Even If You Know The Answer

• 00:00:00

  There is a riddle that seems impossible even if you know the answer. It involves 100 prisoners who can search for their number in 100 boxes in a sealed room. If all prisoners find their number, they will be freed, but if even one fails, they will all be executed. The best strategy to improve their odds from 1/2^100 to nearly one in three involves a mathematical solution. Computer scientist Peter Bro Miltersen came up with this strategy, which was published in a paper with the solution left as an exercise for the reader.

• 00:03:12

  The strategy in the riddle involves going to the box with the number on the slip inside it, and then going to the box with that number on it, repeating this process until finding the slip with your own number. The success of finding your number depends on the length of the loop that includes your number. If the loop is shorter than 50, you will definitely find your slip. However, if the loop is 51 or longer, you are likely to exhaust the 50 boxes you are allowed to search before finding your slip. This strategy gives over a 30% chance of all prisoners finding their number, with the success rate depending on the length of the loop.

• 00:06:00

  The probability of a random arrangement of 100 numbers containing no loops longer than 50 is approximately one in three. To calculate this probability, imagine all the different ways you can connect the 100 boxes to form a loop. The total number of unique loops of length 100 is 100 factorial divided by 100. The probability of any random arrangement of 100 boxes containing a loop of length 100 is 1 over 100. The probability of loops shorter than 50 is calculated by adding up the probabilities of loops of varying lengths, which equals 0.69.

• 00:09:16

  There is a 69% chance of failure for the prisoners, meaning a 31% chance of success where the longest loop is 50 or shorter. The loop strategy increases the probability of each prisoner finding their number to 50%. However, the probabilities are no longer independent of each other. With the loop strategy, all prisoners would find their numbers 31% of the time. If the prisoners choose boxes randomly, around 50 prisoners would find their number in most runs. The prisoners all win or lose together with this strategy because their numbers are guaranteed to be on the loop they are on. The slips and boxes are like Lego bricks, forming loops and preventing dead ends. The warden of the prison is a sadistic mathematical warden.

• 00:12:25

  Prisoners can guarantee success by swapping the contents of just two boxes, breaking any loop longer than 50 into two separate loops shorter than 50. If a malicious guard arranges the boxes to form a loop longer than 50, prisoners can counter by renumbering the boxes. As the number of prisoners increases, their chance of success only slightly decreases. The probability of success approaches a limit calculated using the formula of one minus the chance of failure, which is the sum of areas under the curve of rectangles. As the number of prisoners approaches infinity, this approximation becomes more accurate. The probability of failure is equal to the natural logarithm of two.

• 00:15:28

  This strategy of linking everyone's outcomes together in a loop increases the chance of all prisoners finding their numbers to at least 30%. It is impossible to have just a few people missing their numbers - it's either everyone succeeds or fails completely. If you enjoy puzzles, check out Brilliant, a website and app that offers interactive lessons in math and science. They have courses on various interesting topics, including probability and problem-solving. By visiting brilliant.org/veritasium, you can get 20% off an annual premium subscription. Thank you for watching!