Brain Teaser 29: Prisoner Problem
Hi, I’ve developed a keen interest in brain teasers lately and thought, why not share and discuss them here. These brain teasers could potentially be asked during interviews for quantitative-related roles. They are taken from the book ‘A Practical Guide to Quantitative Finance Interviews’ by Xinfeng Zhou. The problem that we’re gonna solve in this post is “Prisoner Problem”.
Problem:
100 prisoners are given the chance to be set free tomorrow. They are all told that each will be given a red or blue hat to wear. Each prisoner can see everyone else’s hat but not his own. The hat colors are assigned randomly and once the hats are placed on top of each prisoner’s head they cannot communicate with one another in any form, or else they are immediately executed. The prisoners will be called out in random order and the prisoner called out will guess the color of his hat. Each prisoner declares the color of his hat so that everyone else can hear it. If a prisoner guesses correctly the color of his hat, he is set free immediately; otherwise he is executed. They are given the night to come up with a strategy among themselves to save as many prisoners as possible.
Questions:
(1) What is the best strategy they can adopt and how many prisoners can they guarantee to save?
(2) What if there are 3 possible hat colors: red, blue, and white? What is the best strategy they can adopt and how many prisoners can they guarantee to save?
Solution:
(1) Here’s a possible strategy: when they have been assigned a hat, each prisoner will look at the other 99 prisoners and count the number of prisoners with red hats. The first prisoner being called will then declare his hat color according to the following:
- If the number of prisoners with red hats that he sees is even, he declares his own hat to be red.
- If the number of prisoners with red hats that he sees is odd, he declares his own hat to be blue.
In this way, the other 99 prisoners will be able to determine the color of their hats accordingly.
The first prisoner has a 50% chance of guessing his own hat correctly, but he will be able to save all the other 99 prisoners.
(2) In the case of 3 hat colors, we use the following scoring system: red = 0, blue = 1, and white = 2. Each prisoner will look at the other 99 prisoners and count the total score. The first prisoner being called will then declare his hat color according to the following:
- If the score % 3 = 0, he declares his own hat to be red.
- If the score % 3 = 1, he declares his own hat to be blue.
- If the score % 3 = 2, he declares his own hat to be white.
In this way, the other 99 prisoners will be able to determine the color of their hats accordingly. Let s_X be the score counted by prisoner X for the other 98 prisoners that he sees.
The first prisoner has a 1/3 chance of guessing his own hat correctly, but he will be able to save all the other 99 prisoners.
And that’s all for this brain teaser about prisoners 👮. Any feedback or questions are welcome! Are you interested in more brain teasers 🧠? Check out the other problems in this series:
Thank you for reading! :)
