23
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ I accepted my own answer on this question as it provided by far the highest value. Please answer if you have a theory for a better one. I believe there is still likely a better one and will run simulations to prove it. $\endgroup$
    – kaine
    Commented May 30, 2014 at 15:15
  • $\begingroup$ The paper linked contains so many typo error, making it quite confusing to read. $\endgroup$
    – justhalf
    Commented Jun 27, 2014 at 2:31
  • 2
    $\begingroup$ I find this scenario extremely unlikely in real life.... $\endgroup$
    – Jiminion
    Commented Jul 14, 2016 at 16:53
  • 1
    $\begingroup$ @Jiminion and the classic problem is likely? It is a puzzle. $\endgroup$
    – kaine
    Commented Jul 14, 2016 at 16:55
  • $\begingroup$ @kaine, sorry. I was joking. $\endgroup$
    – Jiminion
    Commented Jul 14, 2016 at 19:22

4 Answers 4

Reset to default
13
$\begingroup$

If you accept a probabilistic argument, they can get out (or die) much sooner. After $d$ days, the chance that a given prisoner has seen the room is $1-\left(\frac {99}{100}\right)^d$. It is not fair to consider these all independent, but it will not be far wrong. The chance that all the prisoners have seen the room is then $\left(1-\left(\frac {99}{100}\right)^d\right)^{100}$. If we want a probability of success of $p$, we need to solve $$\displaystyle \left(1-\left(\frac {99}{100}\right)^d\right)^{100}=p\\1-\left(\frac {99}{100}\right)^d=p^{0.01}\\1-p^{0.01}=\left(\frac {99}{100}\right)^d\\d=\frac{\log(1-p^{0.01})}{\log 0.99} $$
giving a result of $$ \begin {array} {r | r}p&d\\ \hline \\0.5 &495\\0.75&582\\0.9&682\\ 0.95&754\\0.99&916\\0.999&1145 \end {array}$$ They can take their choice from this table. Even $99\%$ probability take less than three years.

To get an idea of the error of the independence assumption, at 582 days, the first two stages of an inclusion-exclusion argument give a chance of failure of $0.99^{582}\cdot 100-0.98^{582} {100 \choose 2}=0.2495$ and adding in the chance of $97$ takes it up to $0.2527$ so it is already very close.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ This is simular to the back of the envelope calculation I did before proposing this question. Using this method I got that you would end up with a maximum value at 917 days at the 99% probability. I doubt, however, that just guess on day 917 is the absolute best solution. Is there no way to confirm if you are the right track? Should I remove the fair generator assumption? $\endgroup$
    – kaine
    Commented May 23, 2014 at 18:45
  • 1
    $\begingroup$ To remove it, you have to do an inclusion-exclusion argument. Calculate the chance that only 99 have been selected, but you have double counted the chance that only 98 have been selected, etc. At the higher probabilities of all 100, the values will fall rapidly, so you can quit early. $\endgroup$
    – Ross Millikan
    Commented May 23, 2014 at 19:11
11
$\begingroup$

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).

Improve this answer
$\endgroup$
7
  • $\begingroup$ You make an excellent point. Two nits: the first day, the prisoner should leave the light bulb in a known state-on fits your description. After that, each one should toggle on their first visit. In your paragraph about 495 you are missing "not" in the second line. $\endgroup$
    – Ross Millikan
    Commented May 27, 2014 at 15:48
  • $\begingroup$ Thank you for the correction. My suspicion that this was possible is the only reason I hadn't accepted you answer. $\endgroup$
    – kaine
    Commented May 27, 2014 at 15:51
  • $\begingroup$ I seem to have underestimated the number of ones that had not yet reached 99. The best date is, therefore, not 495 but (by simulation) 692. $\endgroup$
    – kaine
    Commented May 29, 2014 at 13:07
  • 1
    $\begingroup$ @Florian F. That doesnt work. As the Warden can put several in on day 1, they wouldn't know for sure if they are the first ones. $\endgroup$
    – kaine
    Commented Sep 13, 2014 at 19:38
  • 2
    $\begingroup$ You could manipulate the strategy if that were the case but you would lose a day. It isn't cost free like it would be if the Warden let in exactly one each day. $\endgroup$
    – kaine
    Commented Sep 13, 2014 at 20:39
2
$\begingroup$

I am afraid that the formula

p(d) = (1-(99/100)^d)^100

or more generally

p(n,d) = (1-(n-1/n)^d)^n

is wrong. The correct formula is

p(n,d) = n! S(d,n) / n^d,

where S(d,n) denotes the Stirling's number of the 2nd kind (see, e.g., DLMF §26.8 Set Partitions: Stirling Numbers). In the following figure drawn for n = 100, the curve corresponding to the correct (wrong) formula is in blue (red) color. It shows the wrong formula is a fair approximation if d > 250, but the difference becomes significant when d falls below 250, and eventually fails for d<100 (where it should be exactly zero).

enter image description here

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the feedback... I was hoping to see the exact formula when I asked this! I used that approximation because my answer was largely a response to another answer. In his case d~900 and in mine d~500 so the approximation it does look like this was appropriate. Does this provide any insights into how to get them out faster and safer? I still feel both my and Ross's answers are more proofs of concept than legitimate solutions. $\endgroup$
    – kaine
    Commented Apr 2, 2018 at 13:24
  • $\begingroup$ In my opinion, from the practical point of view, the (wrong) formula you provided is a very good approximation for number of day large enough to make the probability (that every prisoner visited the interrogation room) non-negligible. $\endgroup$
    – hlediks
    Commented Apr 2, 2018 at 13:40
  • $\begingroup$ And here is the best account of the riddle: link $\endgroup$
    – hlediks
    Commented Apr 2, 2018 at 13:42
0
$\begingroup$

The solution is this:

The prisons select a fellow, say Alice, who will have a special responsibility. All other prisoners behave according to the same protocol: each turns the light off twice, i.e. they turn it off the first two times they find it on. They leave it untouched thereafter. Alice turns the light on if it was off and, additionally, counts the number of times she entered the room with the light off. When her count reaches 2n - 3 she may claim with certainty that all n prisoners have been to the room.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Um, sorry but that is an answer for the original problem, not this restatement. I will calculate but I think that is the simple counter that takes 30 years. $\endgroup$
    – kaine
    Commented Jul 14, 2016 at 15:47
  • $\begingroup$ Oh and why do you need 2 switch offs? That is needed if the original light position is unknown. $\endgroup$
    – kaine
    Commented Jul 14, 2016 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.