1
$\begingroup$

You may recall the prison experiment done along the following lines:

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 at random, and place him in a central interrogation room made of concrete walls 7ft on all sides and containing only a light bulb affixed to the ceiling with a toggle switch on one wall. The prisoner will be left alone for 1 minute in this room. 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.

The solution to this puzzle (I surprisingly cannot find it on PSE, is found here)

Since that experiment's success, a new, crueler warden has taken over. He does not want the prisoners to succeed in obtaining their freedom. He is bound by law to offer the prisoner's the same opportunity, but he is allowed to change the rules to make it harder for them. To that end, he comes up with a plan that he thinks makes it impossible to succeed.

He removed the lightswitch that controls the bulb from the room. In addition, after each prisoner's time in the central room, he will peer in the room himself and see if anything has been altered or left behind; if he sees any difference, all prisoners will be executed.

Under these new rules, what plan can the prisoners devise to guarantee their freedom?

CLARIFICATION: To help keep the possibilities from being too broad, I want to specify that the answer I have in mind does not involve anything besides the room itself (nothing like 'prisoners banging on their doors if they've visited the room', etc) and can yield a strategy that can guarantee with 100% certainty when all prisoners have visited the room (nothing like 'wait x years and they've probably all been').

$\endgroup$
  • 3
    $\begingroup$ At first glance, it seems like there wouldn't be any algorithmic strategy anymore because there are no more switches to flip, and because every prisoner will see the exact same room when they enter, no differences in room state allowed. $\endgroup$ – Joe Z. Sep 30 '15 at 16:47
  • 1
    $\begingroup$ Link to the original puzzle please? $\endgroup$ – CodeNewbie Sep 30 '15 at 18:34
  • $\begingroup$ @CodeNewbie me too, I'm having a hard time understanding how the solution to this one works without knowing the method of the original puzzle's solution. $\endgroup$ – Raystafarian Oct 1 '15 at 10:17
  • $\begingroup$ @CodeNewbie - For those wanting to know the "original" solution referenced in the answer, please see the following link. It involves turning the light bulb on and off based on certain conditions.... math.washington.edu/~morrow/336_11/papers/yisong.pdf $\endgroup$ – APrough Oct 1 '15 at 12:50
  • $\begingroup$ So I'm rereading and I'm not clear: Can a prisoner be picked twice? $\endgroup$ – user21856 May 4 '16 at 5:12
6
$\begingroup$

Using the same logic in the original answer (of switching the light bulb on and off), you can still use that algorithm by

slightly loosening/tightening the bulb in it's socket. (about a quarter turn or so). The light bulb would still be lit/unlit, but the next prisoner can easily tell the "on/off" state from the "tightness" of the light bulb. And the warden sees no visible difference in the room.

Link to answer by Yisong Song https://www.math.washington.edu/~morrow/336_11/papers/yisong.pdf

$\endgroup$
  • 1
    $\begingroup$ This was in fact my intended answer. Good work $\endgroup$ – NeedAName Sep 30 '15 at 17:20
  • $\begingroup$ If the prisoners may leave the room when they wish, they may be able to use the heat of the bulb - go into a room with the light off, screw the lightbulb in, let it heat up, then unscrew it slightly so that it remains off. If the warden "peers" in specifically, he will not notice a difference. This is, of course, based entirely on the idea that the bulb will still be warm when The Counter walks in. $\endgroup$ – Jake Sep 30 '15 at 20:46
0
$\begingroup$

A person who lives to a ripe old age will live about 30,000 days. Living in prison is unlikely to increase your life expectancy. If being in prison decreases your life expectancy by as much as 1 day, that means your probability of meeting a prison-specific doom is about 1 in 1 billion, each day.

Whether any given prisoner has been in the interrogation chamber is anti-correlated with whether any other prisoner has. After 100 days, the odds of every prisoner having been in the chamber is very small, because if even a single prisoner has been in twice, then at least one other has not been in at all.

However, as time passes, the correlations become smaller. By the time the average number of visits reaches 10, there is very little correlation at all. In other words, as the number of days passed ($N$) becomes large, the probability that any prisoner has not been in the room approaches (assuming independent Poisson distributions):

$$P(N) \approx 100 e^{-{N\over 100}}$$

Using logarithms, we see that when $P(N) = 10^{-9}$, we have $N = 2532$, which is just shy of 7 years.

So in other words, if they do nothing in the room, except at the 7-year point guess that everyone has been in the room, their probability of dying that day is less than it would be if they just went back to their cells.

This plan is faster than the standard plan or any of the alternatives mentioned. Even waiting a mere 5 years would still have less than 1/million chance of being wrong.

$\endgroup$
  • 2
    $\begingroup$ From the OP: "...the answer I have in mind ... can yield a strategy that can guarantee with 100% certainty when all prisoners have visited the room (nothing like 'wait x years and they've probably all been')." $\endgroup$ – GentlePurpleRain Oct 1 '15 at 15:32
-1
$\begingroup$

The way you worded this sounds as though on the 100th day, the last prisoner will be ushered in (one each day starting the day they are isolated). In that case, whoever gets picked on the hundredth day makes the announcement: problem solved.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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