100 Prisoners and a Light 2: Electric Boogaloo

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.