Are You Smarter than 100 Prisoners? This Riddle Stumped Me Until I Simulated It



Spoiler Alert: This Post Has Nothing to Do With AI

I took a day off to run some errands and get caught up on life. Later in the evening, I came across an interesting riddle video called the 100 prisoners riddle on Veritasium. I could not believe what Derek Muller was saying. Nor did I understand how the proposed strategy worked. For a minute I thought the video may have been recorded for April Fools' Day. When all else fails, we trust our Monte Carlo simulations.

The 100 prisoners problem is a fascinating probability puzzle where 100 prisoners must each find their own number in one of 100 drawers to survive. Each prisoner can open only 50 drawers, and they cannot communicate once the search begins. If all prisoners find their respective numbered boxes they will all be pardoned. Even if one person could not get his/her number they will all be executed. At first glance, the odds seem hopelessly low, with a survival probability of about 10−30 if they choose drawers randomly.

However, a clever strategy dramatically improves their chances. By following a specific sequence based on the numbers found, the prisoners can boost their survival probability to over 30%. This strategy, which I have referred to as the "looping strategy" is simply not palatable. I couldn't wrap my head around why the proposed "looping strategy" would work.



So I decided to run a Monte Carlo simulation to test whether the looping strategy actually improves the prisoners' outcomes. I implemented the simulation in Python, which you can view here: GitHub. Running the simulation multiple times demonstrated that the looping strategy does in fact give the prisoners a huge boost in their probability of success!

Seeing the simulation results helped me better understand how the prisoners' chances are dramatically improved by coordinating their efforts with the looping strategy. The distribution of wins from the Monte Carlo trials showed a weird distribution. Once I realized why the distribution was so odd, I started learning why the strategy worked.

In the end, taking some time off for personal matters led me down an unexpected path of logic puzzles and simulations. It was a nice change of pace from my day-to-day work and a fun learn by doing session.

Let me know if you find this quick diversion into recreational math and simulations interesting. I'm always happy to discuss techniques for simulating complex scenarios. Who knows - it may come in handy someday!

Support my work

Comments

Post a Comment

Popular posts from this blog

Existential Risk from Super intelligent Machines

Image
Sometime in mid 2023 Sir Geoffry Hilton announced his resignation from Google to be able to speak freely about existential dangers from AI. For those of us who may not know, Geoffry Hilton is the fatherly figure for Neural Networks. After the first AI winter, when enthusiasm and investment in AI had faded, He continued his research on neural networks, with support from his colleagues at the University of Toronto. In 2018 he and Yoshoa Bengio received the Turing Award for their work. The Turing Award is the equivalent of the Nobel prize for a computer scientist. He also said, “It is not inconceivable that AI could wipe out humanity”. He started a petition to stop AI development and In mid-2023 a group of very he along with other prominent individuals like Bill Gates and Sam Altman signed this statement of AI risk. All of this suggests that we should take their fears seriously. Dr. Andrew NG called for open discussions and I found most arguments favoured anthropomorphized projections o...
Read more

Advantage; Homeloan

Image
Get a home loan save tax. Yes, I'll elaborate on it later but now some quick notes Get a home loan and if you live in it you get up to 1.5Lakh of interest deducted from your taxable income Get a home loan and rent it out; all the interest is delectable form your taxable income. Get your spouse to be a co-applicant on the loan both of you can enjoy the deductions. Up to 1 Lakh of Principle is delectable  from your taxable income (this falls under 80C so your PPF, ULIP, MF etc. is wasted) (Rented out or self-occupied) Use the interactive Tableau dashboard (change the numbers in the boxes) to see how the numbers work for you and what saves most taxes for you. Learn About Tableau You will notice that you will have better tax savings when you rent out your property and stay in a rented house yourselves. when you rent out all your Interest is tax deductible) But if you stay in it yourselves - you only get up to Rs 1.5 lakhs of deductible amount per year. [indirect me...
Read more

Used Car Market and Fuel Pricing

When I was planning on buying a car. I thought I'll buy a used car. Although I was fully aware of  George Akerlof 's  theory  about second hand car market, I decided to take a shot at it.  Because the "reasonable man" , that we so often read about in economics, often has reasons beyond  economics. Reasons like : Leaving the country; don't know what to do with the car;  Bought a new car there is no place to park my old car;  This car is jinxed!   So I downloaded data from  Cardheko  and few other sites and started my cherry hunt. I was convinced that I could use analytics to pick my cherry. Penny (to the Blogger): "Honey, I know you think you are explaining yourselves but you are not." Ok, George Akeflof's Nobel winning theory suggest that there will be no good cars in a used car market because they don't fetch a fair price.  And he refers to good cars as a Cher...
Read more