This would work of course, but is it optimal? For instance, this would also work, I think:

Alice counts the times she finds the light on, and ensures that it is always off when she leaves the room. Everyone else turns on the light the first time they find it off, and then never touches it again. This way, between visits of Alice, at most one prisoner will turn on the light, and no prisoner turns it on more than once. Therefore the number of times Alice finds the light on is no more than the number of different prisoners that have entered the room. Each prisoner knows he has been counted once he has turned the light on, since he is the only one who touched the switch since Alice last visited. When Alice counts to n-1, she knows everyone has visited the room.

What does optimal mean here? It could only reasonably mean that the prisoners are freed in the shortest time. So what is the expected time they must wait until Alice has counted to n-1? This is a rather elaborate calculation in probability, so the prisoners turn to the actuary (who is in prison for embezzlement) for some answers.

He explains that using Bayes theorem, P(X|Y)*P(Y) = P(X&Y) = P(Y|X)*P(X) and the linearity of expected value, E(X|Y)*P(Y) + E(X|~Y)*P(~Y) = E(X) you can calculate the expected time in prison like this:

Suppose Alice has just visited the room, and let K be the number of days that pass before her next visit (so she visits again K+1 days from now), let n be the number of prisoners, let c be the number of times she has found the light on so far, and let P(ON) and P(OFF) be the probabilities that she finds the light on or off on her next visit. Then E(K)=1/n, P(K=k) = 1/n*((n-1)/n)^k, P(K=k|OFF) = 1/n*(c/n)^k, which are fairly obvious.

Bayes theorem then gives P(K=k|OFF) = (1-c/n)*(c/n)^k, and from this you can calculate E(K|OFF) = c/(n-c). and linearity gives E(K|ON) = ((n-1)(n-c)-c/(n-c))/(n-c-1). Now let m be the number of times Alice visits and L be the number of days that pass before she next finds it on. Each time she finds it is off, c does not change, so all the calculations regarding the time until her next visit also do not change.

Therefore, the expected number of days until she next finds the light on is found by summing over all possible m to get the expected total time wasted on visits where the light is off, plus the expected time for the one visit where it was on. This gives E(L) = (1+E(K|ON))P(ON) + sum(m(1+E(K|OFF))P(OFF)^m = n(1/(n-c-1) - 1/(n-c) + 1 - 1/(n-c)^2).

Now we know how long we expect to wait from count = c to count = c+1. Therefore, we must sum this up from c=0 to c=n-2 to find the total expected time E(T). The result is E(T) = n^2 - n/(n-1) - a, where a = sum(1/c^2) from 2 to n. Putting n=100 into this gives 9935.5 days, which is 26.2 years.

But (continues the actuary) this is absurdly long to wait. Simple probability shows that we can be almost certain much sooner than this. The probability that on day d the count is c is P(c,d), which is obviously equal to P(c-1,d-1)*(1-(c-1)/n) + P(c,d-1)*(c/n). Of course, P(0,0) = P(1,1) = 1 and P(1,0) = 0, so we can recursively calculate the probability P(n,d). It turns out that P(100,1146) = 0.999, and P(100,1375) = 0.9999, P(100,1604) = 0.99999, and P(1833) = 0.999999. That means that in 3.14 years, we have a less than 1/1000 chance of failing, and in exactly 5 years and a week, we have less than one in a million chances of failing. I say we should wait 5 years and then say "let us out, we've all seen the light."

As they are about to kill Alice (who was already a member of Mensa) for coming up with a crazy plan to keep them in prison for 26 years, the game theorist (who is in prison for insider trading on the stock market) steps in to point out that this is a losing move. If they kill her now she will never go into the room, and the warden will keep them here forever.

In the happy ending, they let Alice live, and they all get out of prison in 5 years. Strangely, they all decline to join Mensa, preferring to enter actuarial training.

--Stuart Anderson

It's a pleasure seeing you having fun.

>Alice counts the times she finds the light on, and ensures
>that it is always off when she leaves the room. Everyone
>else turns on the light the first time they find it off, and
>then never touches it again. This way, between visits of
>Alice, at most one prisoner will turn on the light, and no
>prisoner turns it on more than once. Therefore the number
>of times Alice finds the light on is no more than the number
>of different prisoners that have entered the room. Each
>prisoner knows he has been counted once he has turned the
>light on, since he is the only one who touched the switch
>since Alice last visited. When Alice counts to n-1, she
>knows everyone has visited the room.

The problem may be in that the original state of the light is not known. You must account for both possibilities.

Your approach will work if originally the light was off. If it was on and Alice counted it as 1, she is bound to cause an action no one of her fellow prisoners would appreciate. However, if she decides to skip the first count and originally the light was off, she will never reach the revelation point.

>
>What does optimal mean here? It could only reasonably mean
>that the prisoners are freed in the shortest time.

Or, perhaps, the least count that would assure the prisoner release.

>Your approach will work if originally the light was off. If
>it was on and Alice counted it as 1, she is bound to cause
>an action no one of her fellow prisoners would appreciate.
>However, if she decides to skip the first count and
>originally the light was off, she will never reach the
>revelation point.
>
Actually, this is easy to fix. Just add a rule that whoever is picked to go to the room the first day must turn out the light, and then revert to the original rules starting from day 2. This adds one day to their 26.2 year wait.

By the way, I am thinking of this problem as a programming problem, in which there is a controlling process (Alice) that receives a series of 1-bit'semaphore flags from some other processes in a message register which is only checked occasionally. Since she can only receive 1 bit, and there is no possibility of somehow encoding extra information into only 1 bit, at most one other prisoner can send her a signal. She must reset the register to a known state so that she can detect the next flag sent, and the other prisoners must not overwrite each other's flags, so only one prisoner may touch the switch between visits from Alice. It was this line of thinking that led me to set up the prisoners' protocol the way I did. This is also where the idea came from in the paragraph just above this one: I am simply initializing the register. It's just "startup code."
>>
>>What does optimal mean here? It could only reasonably mean
>>that the prisoners are freed in the shortest time.
>
>Or, perhaps, the least count that would assure the prisoner
>release.

Well, yes, now that you mention it, although of course the shortest time to freedom would be more to the prisoners' taste. I suspect that the least count would also be the shortest time, but this is not completely clear. For example, Alice needs to count to n-1 in my solution, 2n-3 in yours, but since each prisoner turns the light switch twice, she is twice as likely to detect a signal in the solution you presented, and therefore will increment her count more often. Possibly both solutions lead to approximately the same total waiting time.

Another type of optimality occurs to me now: minimizing the amount of information the other prisoners have to remember. In one solution each prisoner has to remember which of 2 states he is in (I have turned on the light 0 or 1 times before), and in the other, which of 3 states he is in (I have turned on the light 0, 1, or 2 times before). In human terms, the prisoners might forget after a lapse of years, whether they turned the light on once or twice (disastrous!), but they are less likely to forget whether they turned it on at all. In programming terms, the other processes need an internal buffer to hold their current state, and this buffer is smaller (1 bit) with two states than with three states (2 bits). The Alice process needs n states instead of 2n-2 as well.

Come to think of it, this question would make a good problem assignment for an electrical engineering course: design a set of interacting finite state machines with a shared one bit register that solve this problem. In order to do this, they must be good at translating outcome requirements into protocols and protocols into hardware. Of course, most students don't like to be challenged this much, so they would probably complain that the assignment was "unfair."

--Stuart Anderson

I missed that. I just recognised the problem "holistically", as I remembered it from some time ago, without actually reading it.

>Perhaps there are other variants of this
>problem on the internet with different starting assumptions,
>such as an unknown initial bulb state, and the solution you
>presented is for one of those.

Does not look like it. The only discernable difference (besides the initial condition) is that the prisoners are sent to that room "infinitely often, but in a some arbitrary order determined by their jailer." Curious why Winkler settled for 2 actions instead of 1.

>>Your approach will work if originally the light was off. If
>>it was on and Alice counted it as 1, she is bound to cause
>>an action no one of her fellow prisoners would appreciate.
>>However, if she decides to skip the first count and
>>originally the light was off, she will never reach the
>>revelation point.
>>
>Actually, this is easy to fix. Just add a rule that whoever
>is picked to go to the room the first day must turn out the
>light, and then revert to the original rules starting from
>day 2. This adds one day to their 26.2 year wait.

Right.

>By the way, I am thinking of this problem as a programming
>problem, in which there is a controlling process (Alice)
>that receives a series of 1-bit'semaphore flags from some
>other processes in a message register which is only checked
>occasionally.

Winkler spends 1.5 page proving an additional fact that, for n > 2 there could be only 1 controlling process, in the sense that an arrangement wherewith more than 1 fellow gets a chance to determine with certainty that all prisoners went to the room is impossible.

Now, at the risk of appearing denser than I really am, let me quote from your message:

"Suppose Alice has just visited the room, and let K be the number of days that pass before her next visit (so she visits again K 1 days from now), let n be the number of prisoners, ... Then E(K)=1/n,..."

I would assume that, as n grows, the wait period grows as well. Thus E(K)=1/n does not seem right.

That's interesting; it never occured to me to consider more. I should think it was fairly obvious that only one is possible. Ultimately, some single counter (let's say Alice but it could be any of them) must become certain that all the prisoners have visited the room. If there is more than one counter, this information must come at least partly by communication from the other counters. But there is only one channel of communication, and it only holds one bit, so there is no way for a counter to know whether a signal is coming from another counter or a regular prisoner. Therefore it is impossible for a counter to respond differently to another counter than to a prisoner, so the counter must simply increment her count, just as she would with an regular prisoner.

Therefore the only signal a counter can send to another counter means "increment your count." Her only choice is of the circumstances under which to send it. If she is to transmit to other counters the number of prisoners she has counted, she must signal once for each such prisoner. But she has no control over who receives the signal--in fact, she may receive it herself, and will have no way to know. Therefore, she might increment her own count, and thus overcount the prisoners. This of course destroys the whole scheme.

>I would assume that, as n grows, the wait period grows as
>well. Thus E(K)=1/n does not seem right.

Thanks, that was my mistake. I worked this out on a blackboard, misread my own handwriting and typed what I saw. It'should be E(K)=n-1, which I misread as n^(-1) and typed as 1/n, completely obscuring the connection to the original. The calculations are of course based on the correct value, n-1.

I see that Sheridan beat me to posting the way around the problem of an indeterminate initial bulb state. That's what I get for taking so long writing without checking the page for updates.

--Stuart Anderson

If the first time you see the bulb it is on, turn it off and then never change it again. When you next see it on, declare that all prisoners have visited the room.

If the first time you see the bulb it is off, turn it on and then never change it again.

Then certainly they will be freed, but there is no controlling process. It is possible to set up strategies with no controlling process in all the variations I am aware of. However, there are some variations in which there must be a single process which obeys different rules to the others.

Thankyou

sfwc
<><

Prisoner A enters the room on day one and finds the light off, so he turns it on.
Prisoner B enters the room on day two and finds the light on, so he turns it off and notes that he first saw the light on.
Prisoner C enters the room on day three and finds the light off, so he turns it on.
By chance, Prisoner B is called again to the room on day four, finds the light on, reports that everyone has entered the room, and the prisoners are all killed.

Obviously they cannot all have visited by day 4 if there are 100 prisoners. Am I missing something?

--Stuart Anderson

Never mind; I missed seeing your first paragraph because there was no space between it and the quoted material. Sorry! Your example certainly seems to work for three prisoners. Do you have any examples of strategies that work with many prisoners and yet have no single overall controlling process?

--Stuart Anderson

One day Alice wins them all their freedom by declaring that they have all been in the room. The previous day, of course, Bob was in the switch room. Because he had been in so often, he had gathered a lot of information. As much, in fact, as Alice has the following day. So he knew that everyone had been in the room. But he pedantically stuck to the strategy as given and did not declare this fact. This caused him a good deal of frustration, which was not helped by the warden's evil cackling at the success of his ploy.

Now, with hindsight, Bob concieves of a new strategy, just like the old one except that a person in his situation may declare that everyone has in fact been in the room. Of course this strategy is certain to work, but it now has no single overall controlling process, since any of the prisoners may make the declaration which wins them their freedom. This is an example of such a cheating strategy.

However, it may be shown for some versions of the problem that if there are at least 4 prisoners there is at least one prisoner in any winning strategy who follows a set of rules different to the rules of any other prisoner.

Thankyou

sfwc
<><

I just remembered of my intention to give your response more publicity than it gets in the forum, as it certainly deserves. I thus made a page out of it, of which I hope you approve.

(https://www.cut-the-knot.org/Probability/LightBulbs.shtml)

Thank you,
Alex

Yes, thank you! I am very happy that you thought well enough of it to include it as a page.

However, I was embarrassed to find that I had made a typo in one of the formulas in my original post:

In the paragraph

Suppose Alice has just visited the room, and let K be the number of days that pass before her next visit (so she visits again K+1 days from now), let n be the number of prisoners, let c be the number of times she has found the light on so far, and let P(ON) and P(OFF) be the probabilities that she finds the light on or off on her next visit. Then E(K) = 1/n, P(K=k) = 1/n·((n-1)/n)^k, P(K = k|OFF) = 1/n·(c/n)^k, which are fairly obvious.

the very last formula should be P(K = k & OFF) = 1/n·(c/n)^k.

Also, since it it now a separate page on its own, it might be nice to clarify one step of the calculation for those who didn't read it in the context of the thread. Since you have to calculate P(OFF) before you can apply Bayes theorem, I would suggest adding the following sentence at the start of the very next paragraph:

"Summing the last formula over all k gives P(OFF) = 1/(n-c)."

Thanks again for making a page out of this.

--Stuart

There is one more typo to fix. This is one that you noticed in post #6 of this thread and I corrected in post #7 (quoted below). But it was long enough ago now that we both forgot about it.

>>I would assume that, as n grows, the wait period grows as
>>well. Thus E(K)=1/n does not seem right.

>Thanks, that was my mistake. I worked this out on a blackboard, >misread my own handwriting and typed what I saw. It'should be >E(K)=n-1, which I misread as n^(-1) and typed as 1/n, completely >obscuring the connection to the original. The calculations are of >course based on the correct value, n-1.

Sorry for the extra work, and thanks again for making a page out of this posting.

--Stuart

I am away from my computer. Will fix this on my return.

Thank you,
Alex

Each of n prisoners will be sent alone into a room, infinitely often, but in some arbitrary order determined by their jailer. The prisoners have a chance to confer in advance, but once the visits begin, their only means of communication will be via a light in the room which they can turn on or off. Help them design a protocol which will ensure that some prisoner will eventually be able to deduce that everyone has visited the room.

Peter's reply was this:

The reason you need two actions is that my puzzle is tougher: the prisoners are not sent to the room once per day, but on an unknown schedule. Thus you can't solve the unknown-initial-state problem by having the first prisoner turn off the light, as he will not know if he is the first.

The two problems are thus related but are not quite the same.

The way I see it there are at least three related but distinct puzzles of varying complexity based on the initial switch position and whether or not a known schedule is followed. The situation where the initial switch position is unknown is included for completeness even though the original post clearly stated that it was 'off'.

A.) First is the situation where the initial position of the switch is unknown, and the prisoners are called at arbitrary intervals (who starts is unknown). This is clearly going to take the most time to free the prisoners. This is where it is necessary to select a 'captain' beforehand who will need to count how many times (s)he turns out the light. Everyone else will need to turn on the light the first two times that they find it off, and leave it alone the rest of the time. In this case the captain can make the claim after finding the light on 2n-2 times.

B.) Second is when the initial switch position is known but the prisoners are called arbitrarily. For the sake of convenience (and consistency with the problem statement) let's say that the switch is initially off. Again, nobody knows if they are first so it is necessary to select a captain beforehand who will maintain a count and turn the switch off whenever (s)he finds it on. Everyone else will turn it on the first time they find it off and leave it alone every other time. This second scenario will require the captain to find the switch on n-1 times before making the claim.

There is very little that can be done to make either of the first two processes more efficient. It is possible for all of the prisoners to keep a count of how many times they find the light off, then find it on, and then making the claim before the captain is called to the room, but the likelihood of this being of any value is remote. This would require a claimant, other than the captain to make at least two visits between each and every pair of visits by the captain. Probably not valuable for any large n (but it may be a way to pass the time in solitary).

C.) The third situation is the most fascinating. The starting time and intervals are known to the prisoners (e.g. every night after supper, starting tomorrow.) This scenario allows the prisoners to pass additional knowledge through the switch. Here is my strategy, which I believe is optimal:

To begin with, the initial position of the switch is irrelevant if everyone knows when the process begins. The first person turns it on or leaves it on. Period.

As in B.) above everyone but the captain will turn the switch on the first time they find it off, and leave it alone on every other visit.

The captain has the dual responsibilities of turning the switch off and maintaining a count of visitors (how many times did I turn it off?). This is the same as in A.) and B.), however, it is not necessary to preassign the captain!

There are additional responsibilities and exceptions for the first few visitors that make use of the knowledge implicit in knowing which day they are called. This additional knowledge can shave huge amounts of time off the sentence (for n=100 roughly 300 days? Again, I'll leave that to the more skilled mathematicians). These time saving, knowledge passing devices are as follows:

Day #1: The first person (knowing that they are first) turns the switch on or leaves it on (this is why the initial position is irrelevant).

Day #2: The second person (knowing that they are second; this is important!) will find the switch on. They know in advance that the switch will be on! EVERYBODY knows that the second person will find the switch on! This provides an opportunity to pass on valuable information! The second person simply leaves the switch on. If, however, the second person was also the day #1 visitor they turn the switch off! This passes information to the day #3 visitor!

Day #3: The third person can find the switch in either the on/off position. (They are receiving valuable information!) The third person can also be a repeat visitor. If (s)he finds the switch on and is not a repeat visitor (s)he leaves the switch on! This lets the Day #4 visitor know that there have been three previous visitors. If the Day #3 person finds the switch off, or is a repeat visitor, they become the 'captain'. (S)he knows how many people have visited the room, (only one other, or none if this is his/her third visit) and it is now up to this newly assigned captain to count the rest of the visitors. This Day #3 visitor makes sure the switch is off and leaves the room with the responsibility of captaincy. This says to the Day #4 visitor, "I am the captain because you have no way of knowing how many visitors have gone before (either one or two)".

Day #4: The person who enters on day #4 will either find the switch off, in which case they follow the normal rules, or they will find the switch on. If the switch is on, they become the captain and know that there had been three different previous visitors (unless they themselves had visited previously, in which case the count is only two).

Day #5 and on: Follow the original rules: on first finding the switch off, turn it on otherwise leave it alone.

It is clear that by dynamically selecting the captain, instead of preselecting, you have guaranteed that by day #3 or #4 you have had your captain visit and the countdown is under way. In fact you are over 94% sure to have a count of 3 by day #4. This is clearly superior to waiting until a preselected captain is called into the room, only to start with a count of 1.

One additional possibility to consider: Is it possible, under the rules to have the visitors unscrew or tighten the light bulb? This could pass even more knowledge, and a higher count to a captain to be determined later than day #4.

Thanks for the great puzzle.

>A.) First is the situation where the initial position of the
>switch is unknown, and the prisoners are called at arbitrary
>intervals (who starts is unknown). This is clearly going to
>take the most time to free the prisoners. This is where it
>is necessary to select a 'captain' beforehand who will need
>to count how many times (s)he turns out the light. Everyone
>else will need to turn on the light the first two times that
>they find it off, and leave it alone the rest of the time.
>In this case the captain can make the claim after finding
>the light on 2n-2 times.

I belive that for n being a large number (let's not discuss what a large number is), we can simply have a captain that counts the number of times he turns the light to the "off" position, as well as a second person, who will turn the light on twice. Everyone else will turn the light on only once, when the find it at the "off" position.
Like this, the captain will only have to count to {n} number of times, which is usually smaller than 2n-2.

However, my solution has a few holes.

The first one I saw is that if the captain comes first and sees the light "on", he will consider that someone has already been in the room. Like that, when he will count to n times. However, it is possible that ONE person has not yet been in the room. I believe (again, I might be mistaking) that we can overlook this problem because we have a hundred prisoners, and chances of such a situation are very slim.

If there is anything else I haven't seen please inform me.

Thank you

P.S. If you want to unscrew the light bulb, you should simply break it into pieces, put all of them in a pile in one end of the room, and when a person comes into the room for the first time, they put a piece of glass from the pile into the center of the room. When there will be 100 glass pieces in the center, everyone would have visited the room. (note: this could not work for large groups)
Yes, I know that this is not the CORRECT or mathematical solution that we are expected to give.

>However, my solution has a few holes.
It does indeed. I have tried to avoid these holes by having everyone but the captain turn the light on twice.

>However, it is possible that ONE person has not yet
>been in the room. I believe (again, I might be mistaking)
>that we can overlook this problem because we have a hundred
>prisoners, and chances of such a situation are very slim.
>
Slim chance, yes but still possible. The claimer was to be 100% certain.

The captain changes the switch no matter what. Any prisoner will turn the light to the "off" if, and only:

1. they have never done it before
2. they have seen the light in BOTH positions
3. the light is "on" when they enter the room.

Thus, the solution has no chance of failure because when the light is switched for the first time, we can be assured that the captain was already in the room and that the original position of the switch would have no impact.

>Slim chance, yes but still possible. The claimer was to be 100% certain.
This condition is also fulfilled in this solution.

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."
is best.

Do you have the proof that it is the best solution?

Not a logical answer but a correct one given the limitations of the problem, since you never mention how long each sentence is for the prisoners, the most simple answer is, only when the last prisoner is left can he make that assertion. It's not logical but it is lateral.

They simply agree not to play the game until there is only one prisoner left.

All one hundred prisoners must of been there, since it's a central room. Even if by chance one prisoner never went there it is true, since it's random this is a possibility. We don't know the duration of their sentences, and even if we did it doesn't matter. Even if they died, they would be carried out through the central room to be buried. In this situation and given the fact that the light bulb is irelevant, it's a possible answer. because the only remaining prisoner is taken out every day.

Or this is my logical answer: every prisoner records if they have never been in the room before by saying: never = down position light off, if you see a down you note it and then proceed by either leaving it down meaning you also have never been in the room before, or by flipping it up(light on) Saying the previous person had not been in the room before but you have: unless you have been in the room before and the light switch was in the up position, then you flip it down as if you have never been in the room before.

When you see 50?(x) consecutive light down(off) Then you make the assertion that everyone has been in the room.

MNot sure of the exact number but I'll leave that for now as it's the principal that is important.

Essentially the answer is as soon as you see x number of down switches you call the warden, x is 50 or 100 depending on how long you've been there using a simple algorythm should reproduce this result.

They simply agree not to play the game until there is only one prisoner left.

All one hundred prisoners must of been there, since it's a central room. Even if by chance one prisoner never went there it is true, since it's random this is a possibility. We don't know the duration of their sentences, and even if we did it doesn't matter. Even if they died, they would be carried out through the central room to be buried. In this situation and given the fact that the light bulb is irelevant, it's a possible answer. because the only remaining prisoner is taken out every day.

Or this is my logical answer: every prisoner records if they have never been in the room before by saying: never = down position light off, if you see a down you note it and then proceed by either leaving it down meaning you also have never been in the room before, or by flipping it up(light on) Saying the previous person had not been in the room before but you have: unless you have been in the room before and the light switch was in the up position, then you flip it down as if you have never been in the room before.

Once you have been in the room 50 times and seen 50 consecutive up(light on) and then not necessarily after that but when you see 50 consecutive light down(off) Then you make the assertion that everyone has been in the room.

It came to me in a dream well not really I just figured it out, do I win a prize?

The answer is to watch the patterns of switches, and if you have been in the room with enough frequency x/t times the pattern will be mostly down, mostly up,mostly down, always up, always up or down number of times in the romm/days you can predict with certainty whether the switch will be up or down, once you can do this x number of times making it statistically impossible. you call the warden. If x/t is above y and you have been there x times, then you can claim to have the only possible answer by probability and if your a frequent enough visitor by virtual certainty, everyone has been there.

Where y=number of years.

My suggested alternate solution

One prisoner thinks 100 days between going to living room (on average) x 99 prisoners at least. 27 years to get out (law of averages.) It feels wrong. Something is really wrong.

Well he thought, what are the chances all the people have gone into the living room after a year, after 2 years etc...

The possibility all 100 people are chosen after a given number of years is:

Mathematica notation:

sum((-1)^k*(100!/((100-k)!*k!) * (100 - k)^(y*365))/100^(y*365),{k,0,100})

Where (y*365) is the number of days, y is the years (it's in there twice)

Latex notation

100^{-365y}\sum_{k=0}^{100}{(-1)^k}{100 \choose k}(100-k)^{365y}

So he will make the claim sometime after 4-5 years. Some designated counter can count whatever lights he wants, but he will free all 100 thanks to the laws of probability. He saved them each over 20 years in jail. That’s over 2,000 man years.

Phew….
My chart

Even more precise, but not significant in the outcome is:

Where t is the number of times he has already been in the living room

Conditions

If t=0 then there is no chance what so ever.
If 365y-t<99 no chance what so ever.

Latex

99^{-365y-t}{\sum_{k=0}^{99}{(-1)^k}{99 \choose k}(99-k)^{365y-t}}

Mathematica

sum((-1)^k*(99!/((99-k)!*k!) * (99 - k)^(y*365-t))/99^(y*365-t),{k,0,99})

Years
1 6.9011% or 14 in 15 of Mass Excecution
2 93.7616% or 1 in 600
3 99.8373% or 1 in 15.8
4 99.9958% or 1 in 23,500
5 99.9998% or 1 in 924,000
6 99.99999724% or 1 in 36.2 million
7 99.99999993% or 1 in 2.4 billion
8 99.999999999% or 1 in 55.6 billion
9 99.999999999... or 1 in 2.18 trillion
10 99.999999999... or 1 in 85.4 trillion (the people on 13,000 planets with equal populations to earth)

Any way I tested the math with a probability chart and 2, 3 and 4 prisoners and up to 10 days. It computes.

For my calculations I eventually settled on this Assuming he is chosen about 3.65 times in each year.

Sum<(-1)^k*Binomial(99,k) * (99 - k)^(Round(361.60*2))/(99^(Round(361.60*2))),{k,0,100}>
<MATH>
\sum_{k=0}^{99}{(-1)^k}{99 \choose k}(99-k)^{361.6y}99^{-361.6y}
</MATH>
https://www.codecogs.com/eqnedit.php?latex=\sum_{k=0}^{99}{(-1)^k}{99 \choose k}(99-k)^{361.6y}99^{-361.6y}

And thank you for intriducing us to https://www.codecogs.com. I was unaware of the existence of this site.