One Hundred Prisoners

[Paleophyte]

OK, this isn't the standard 100 Prisoners problem that has become so YouTube famous that it obscures the solution to all other 100 Prisoner problems. There will be no boxes.

The Problem:

There are 100 Prisoners being condemned to prison for all eternity.

Everybody in this scenario behaves purely logically and flawlessly, including not dying unless told to by the rules.

Prior to being incarcerated, the Prisoners are allowed to strategize. They will have no direct communication once their sentence begins.

Once their sentence begins, one prisoner will be selected purely at random* each day. That prisoner will be taken to a room with a light and a switch. The light may be turned on or off, but may not be manipulated in any other manner**.

Once they are certain*** that every prisoner has been in the room at least once, they may ask to be released. If they're right then they'll be freed, but if they're wrong they'll be executed.

---

* These probabilities are independent and truly random. It's unlikely, but entirely possible, that one prisoner might be selected at random for twenty days in a row. It's possible that a prisoner might not be selected for years or decades. There is no rotation, roster, or schedule that ensures that each prisoner enters the room at a regular interval.

** Treat the room with the light and the switch as a single-bit transmitter. Do not manipulate the bulb.

*** We want mathematical certainty here. These prisoners appear to be immortal, so any risk of dying is too great. It's simple enough to wait for an acceptable level of danger to have passed and ask for out, but we aren't going to use those probabilistic approaches.

---

OK, that's it. I think that I have both a brute force and an optimized solution. The brute force approach works, but it takes geological time. The optimized strategy might be viable within a human lifespan, maybe faster. I was wondering if there were quicker approaches and if anybody with a math/computing background knew how to calculate the time for the strategy to succeed.

Brute Force Strategy:

---

 - Assign each prisoner a number, 1 to 100.
 - Assign each day a number, 1 to 100, looping back to 1 when we pass 100.
 - If the prisoner enters the room on Day = Their Number then they switch the light on, otherwise they switch it off. This communicates to the next prisoner in the room that the previously numbered prisoner was in the room.
 - Once a prisoner has seen that the light is on for all of the other prisoners, they ask to be released.

The downside is that this takes geological time to transmit information. The information is only generated when a prisoner's number matches their day, and the effective transmission rate declines as the audience becomes saturated with prisoners who already know that you've been in the room. The final state before release is a very small population of prisoners who aren't accounted for attempting to communicate with a small population of prisoners who don't know that they've been in the room. We're left at the end with a prisoner who has managed to account for 98 of his fellow inmates and is just waiting on word from that final 99th.

---

Optimized Strategy:

---

As above, but with a single modification that improves data transmission speed.
 - Once a prisoner knows that another prisoner has been in the room, they may act as a proxy for them, turning the light on if they're in the room on that prisoner's day. We don't care who turns the light on, only that the fact that they were in the room at some point gets transmitted.

So Prisoner 62 happens to be in the room on Day 37 and sees the light on. This tells them that Prisoner 36 was in the room on Day 36. So when Prisoner 62 finds themselves in the room many rotations later on Day 36, they turn the light on. This reduces wasted transmission of data and minimizes those final moments waiting for that last bit of data on a final prisoner to slot into place.

---