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

Virus: Discussing macroscopic possibilities

Image
Our world view is limited by our own senses and our size and scale. I am throwing out a possibility of studying viruses through another lens.  Many people believe that COVID-19 is the mother earth’s fight against human infection [ 0 ] . It is quite possible that viruses are earth’s antibodies trying to keep the earth healthy. Viruses are known to keep the balance and diversity of microbes in the oceans.   [1]   Viruses have been eliminating species that run wild since the beginning of life on earth. They are a major driver in human evolution [   2 ][   3 ] . Recent studies have shown that viruses could have been the reason we have life on earth. [   4 ][   5 ] So, there is more to viruses than it is commonly known. In this blog, I would like to discuss the possibility of studying viruses through another lens. Allow me to take you through some seemingly unrelated illustrations to make my point.   Every mammal on this planet instinctively develops a...
Read more