There is a classic problem below for which Dr. Yisong Song wrote a very well written and thought out series of solutions. The variation here I've never seen anywhere but am curious. I want to work it out myself but think others may also want to give it a go.
One hundred prisoners have been newly ushered into prison. The warden tells them that starting tomorrow, each of them will be placed in an isolated cell, unable to communicate amongst each other. Each day, the warden will choose one of the prisoners uniformly at random with replacement, and place him in a central interrogation room containing only a light bulb with a toggle switch. The prisoner will be able to observe the current state of the light bulb. If he wishes, he can toggle the light bulb. He also has the option of announcing that he believes all prisoners have visited the interrogation room at some point in time. If this announcement is true, then all prisoners are set free, but if it is false, all prisoners are executed. The warden leaves, and the prisoners huddle together to discuss their fate. Can they agree on a protocol that will guarantee their freedom.
For this variation, there is a set of such 100 prisoners who are all exactly 50 years old and reasonably expect to live to 80. The light starts off and they will be taken into room on average roughly once a day. The warden may, however, send an extra prisoner of his choosing to the cell on the same day (but they still never see each other) to disrupt strategies. This excludes the use of binanary token strategy. Because the warden is not completely sadistic, a fair random number generator picks the first prisoners each day.
In their meeting, they initially agree to a simple one counter solution when one prisoner remembers (having once been a puzzle fan) that this should take about 30 years if they are lucky. He argues that each year outside of prison has an equal value but each year in prison is no better or worse than being dead. Being released on his 80th birthday is therefore worth about the same as never being released at all. He would gladly accept a 50% chance of death to be released with 20 years left of life remaining compared to a 100% chance of survival but being 79 when that chance came.
So if the value of making a guess is the number of years remaining of life multiplied by the probability of surviving the guess, what strategy should they employ to maximize this value?
Answer
I still believe there is a better answer than this but that this is a significant improvement over the current best answer. I have used only the same math used by Mr. Millikan as I like how understandable it made the problem.
On day 917, according to the
$\displaystyle \left(1-\left(\frac {99}{100}\right)^d\right)^{100}=p$
used by Mr. Ross Milikan the value has a maximum with only a roughly 1% chance of everyone being executed horribly. This does not use the light bulb at all and the likelyhood of more than 1 person never having been in the room is less than .001%.
Strategize that every time a prisoner (assumed to be all male) walks into the room the first time, he switches the light. After the 100th person goes in the room for the first time the light will always be off. On day 917, if the light is on: they know the 1% chance has happened and they must wait for it to go off before they say everyone has been there. The likelyhood that there are 2 people who have not been there so the light was off but they die is very small.
If this strategy is used on day 495 (for instance). The probability that everyone has been there is under 50%. The probability that 2 people have not been there, however, is less than 1%. Therefore, on day 495 if the light is off they can guess with >98% certainty that they can be freed; if the light is on, the person who has not been there yet, turns off the light and guesses that everyone is there and they win on the first day it is true.
Unless my calculations are too approximated, this strategy could yield a larger likelyhood of survival and will likely release prisonners a year ealier than Mr. Millikan's (depending on they day they choose). This strategy has a large likelyhood of releasing the prisonners on the first day possible (but of course still has a non-zero chance of causing horrible death).
No comments:
Post a Comment