100 prisoners and a lightbulb

[Drostie]

Lessee: For normal and variant 1:

"All right, guys, so we're going to play tag. I'm it. When I'm in the room, I'll turn the light on. If you see the light on, and you haven't been tagged yet, you're now out -- turn the light off, and no more touching. Once I think I've tagged all of you, I'll declare that to the captain. I'll figure out the exact odds during the initial phase of the game, because it will take a lot of time to tag all of you; but basically, I'll keep a good count for N light bulbs in a row, and when I see them, I'll declare with 99.99% certainty that you all have been tagged."

The initial phase of that will take damned near forever, though -- it'll take just 100 days on average for me to go in the first time; and there will be something like 100-200-ish of those intervals, for something like ~55 years.

Modifications:

(1) If the prisoners can tell time well enough to determine whether they're the first prisoner or not, then the first prisoner will be "it." This will work for robots-who-can-tell-time (Variant (2) but not (1)) because it can, indeed, be programmed. It will also speed up variant (0) a little. Combining (1) and (2) can be done with the above algorithm, plus some sort of straw-drawing competition among the robots -- the exact method I'd still need to work out.

(2) This probably will go much faster if you let prisoners "tag" an additional prisoner before they're "out." So, a prisoner who has been tagged leaves the light on the first time he sees it, and just remembers that he's been tagged. The second time he gets tagged, he turns it off. the next three times he sees the light, either turns it on or leaves it on. I'd imagine I could design for that; since then the swarm exhausts itself in a very fast fashion. Such a strategy might even take it under the 10-year mark -- though I'm not sure about that.

[Drostie]

Alternatively: The warden is the Guy With The Hat. He uses this as his random number generator, and the prisoners commit seppuku.

Edit: To save y'all from seeing my icon three times in a row: After playing around with a computer simulation, I realized that really, if I'm going to do a statistical confidence thing, I might as well do it the following way:

Represent this series like a Markov Chain. We have that

(0) transitions to (1) with probability 100/100
(1) transitions to (2) with probability 99/100
(2) transitions to (3) with probability 98/100

...and so on, with (N) being a bin that represents N unique visitors who have visited the room. The time T to get to (100) is just a sum of 100 independent geometric random variables:

[T] = [Geom(100/100)] + [Geom(99/100)] + ... + [Geom(1/100)].

The mean of these is 100(1/100 + 1/99 + ... + 1), in other words, 100 times the 100th harmonic number. Which is roughly 520. (I have done this exact same analysis before in another context -- how high your BitTorrent ratio needs to be before you'd expect to have uploaded one of each piece of the torrent to the entire swarm, assuming totally random picks.)

Variance is pseudolinear; and so a quick calculation of the standard deviation gives ~13. Now, this is probably not a normal distribution; but it's still fated to have most of its variation happen within, say, 5-10 standard deviations of the mean. Let's say 10, so that's 130, so 650 days pass, roughly, before we can be highly certain that we're all accounted for.

So, lets just appoint one person to say that we're done after he believes that we've been in there for more than 650 days. If he waits until he's been brought to the light room N times, then that's a sum of N identical geometric random variables with probability 1/100. A rough use of the central limit theorem says that we should look at this sum as roughly a normal random variable with mean 100 N and standard deviation 100 sqrt(N). Z = 6.5/sqrt(N) - sqrt(N) needs to map to a probability of 0.001 or lower. This happens at roughly N = 21, for a typical wait of 2100 days, or under 6 years. So, 2100 days for 99.9% confidence; 2500 for 99.99% confidence, etc.

It turns out that, numerically speaking, my above algorithm does not do better than this, even with optimizations -- it just keeps people busy playing tag until the original starter decides to end it.

This is more readily generalizable to robots, since you can set N higher to compensate for the fact that you're looking at a minimum of random variables.

[Lenoxus]

So I'm bumping this zombie thread instead of replying to the recent "Limbo" puzzle thread ( viewtopic.php?f=3&t=79935 ), because it seems like that's the expected local etiquette? I may be wrong about that. No matter, because my question is indeed about the puzzle in its original form. I think.

So far as I can tell, the "correct" answer is:

Spoiler:

One designated prisoner, the "master", always turns the light on, while everyone else always turns it off.

My problem with this is:

Spoiler:

Suppose that the pattern is, prisoner A and prisoner B keep being chosen alternately, indefinitely (though still by sheer chance). A is the master. So, A is picked first, sees the light off, doesn't know whether he was there first, and switches it on. Then B goes in. B deduces that the last person in the room was A, but can't tell anything else. B switches it off. A sees the light off, deduces that one or more other people were there between his last visit, and switches it on. Etc.

Now suppose the pattern is instead one that, if they all knew about it, would make the prisoners very happy indeed (but they don't know, of course): A goes, then B goes, then C goes, then D goes, etc, looping back to A. This means that A always sees a light that was switched off, and thus deduces that some number of others were there after his last visit (but not which ones, or how many). B always sees a light that was on, deduces that A was there last, switches it off. C through Z (here representing prisoner # 100) each see a light that was off and know that either A hasn't been there at all, or A was there but then someone else came in before. After Z, A comes in and the process repeats.

As far as I can tell, both situations look identical for A and B. So how is anyone, master or otherwise, supposed to figure out when exactly they've all visited it? It seems that there's just about no way for the binary switch to single-handedly give enough information. Are they all factoring in something about what day it is? I'd assumed the situation was "timeless", but maybe not.

Most likely, my understanding of the solution is simply very incomplete.

[Lenoxus]

i think the 100 prisoners can only talk to each other together once for a strategy and then they can't communicate because if that weren't the case each one would just shout "i was in"

so here's the solution:

make one the master, only he may turn the switch on

if someone other goes in and
- the light is on he turns it off, but only if hasn't turned it off once, otherwise let it be

- the light is off let it be

each time the master turns the light on he counts one up
so if he counts to 99 all other were in there, but problem is what happens if light was off at beginning and master comes in first, would be a problem, or not?
no

each one may turn light off 2 times and master counts 2*99-1, so he might miss a second one from one person but that doesn't matter because everyone just has to be in at least once

Oh, wait, I get this now. That's clever! Here's my rephrasing of it:

One person is designated the Alpha. The other 99 people are designated Betas. The rules are:

If you are the Alpha, you keep a mental count in your head starting at 0. If you enter a room with the light off, then you switch it on and add 1 to your mental count. If you enter a room with the light on, then you do nothing. The moment your count reaches 197, alert the warden.

If you are a Beta and you see the switch off, do nothing. If you see it on, then turn it off and henceforth consider yourself a Gamma rather than a Beta.

If you are a Gamma and you see the switch off, do nothing. If you see it on, then turn it off and henceforth consider yourself a Delta rather than a Gamma.

If you are a Delta, you don't do anything at all.

In general, the only way for the light to be off, apart from right at the beginning, is if someone has visited for either the first or second time. Eventually, the Alpha's count of the number of these occurrences will reach 197, and as it happens, it can't ever exceed that (I think). At 197, it must be the case that everyone except one person visited twice, and the one remaining person visted once, or something like that.

It also seems that the solution can be pretty easily generalized so that the prisoner has to deduce when each person has visited the room at least 2 times, at least 3, etc.

[Gwydion]

At 197, it must be the case that everyone except one person visited twice, and the one remaining person visted once, or something like that.

198. If the light starts off and the Alpha is first, then one can imagine a situation in which some prisoner Px never visits the room, but all the others visit the room twice, turn off the light twice, and the Alpha will get to 197 without Px ever turning it on. If the light starts on, on the other hand, we'll never reach 198 until everyone has turned if off twice, but at least we'd be certain.