I think the problem wording is a little vague and that the attempts to help have hindered. The statement "random" in conjunction with "But, given enough time, everyone will eventually visit the switch room as many times as everyone else" means that the distribution is uniform (all equally likely). The statement that he "MIGHT" pick a single person three times in a row indicates that each selection is independent of the ones that went before. I think he was just trying to say this in a way that was not intimidating for his audience.

No time for solutions at the moment, but here are 3 paths.

1. Cheat. Each person has a location wrt the switch box and makes a small indentation with fingernail on his first visit, but never again. The first person to realize that all the positions have been ticked off, announces to the warden.


2. Probability. When a person is picked the first time, he doesn't know if he was the first person picked or not, but he knows, if the choices are independent, that the odds are pretty rare that he would be picked 10 times in a row. Chances are also slim that there were 11 picks or 12 picks or even 20 picks. Blah blah blah. The source distribution is uniform, but the CLT (central limit theorem) says that any distribution will approach a normal distribution in the limit. Let success = I get picked. Let M = # times I am picked. Let N = total number of picks (which I do not know); however, I can compute the binomial for it (in my copious time in my cell). Blah blah blah ... handwaving ... fake out ... mental laziness ... miscellaneous BS ... eventually you realize that once you go, say, 20 times, that the chances that someone is left who has not yet gone are pretty small. Without doing the math (which is not hard, but I'd have to think about it), we could just guess and say 20 ... if I get in this room 20 times then the chances that there is someone who has not gotten in the room are negligible.


3. Again, no solution. Just a path. Some observations.

The states are 00, 01, 10, 11. Label them A, B, D, C, with each state representing two bits of information.

A state diagram shows how the state CAN change, but I can't figure
how to draw one in here. A connects to B connects to C connects to D connects back to A. Draw lines that connect each of them in each direction. An outer ring of lines going clockwise and an inner ring of lines going counter-clockwise.

Each person knows whether he has visited the room, but needs to know the state of the other 22. This means he needs to know 22 bits of information WHEN the 22 bits are all on. Since the states can only represent two bits, we realize the states alone do not represent sufficient info.

However, each individual knows not just the current state, but all the previous states he has seen. Each observation is two bits. He needs to know 22 bits of information; therefore, there is an absolute minimum of 11 visits anyone can make to be certain of the other states (assuming it's possible, which we're not sure of at this point).

We can imagine that each individual is a turing machine. He has a tape which is a memory of what he has seen in the room. (It's not clear at the moment whether it's better to think of this as a two tape or three tape machine, but of course they are equally powerful. We just choose whichever is easier.) So each prisoner is a turing machine. He looks at the current letter on the tape AND all of the past letters and determines what the next letter is that he should write on the tape. The question is this: Is there a program for this TM (turing machine) that can answer this question.

Well, I've gotta go right now. That's as far as I've gotten in a few minutes. No idea these idea will be fruitful or dead-ends, but so far I'm inclined to cheat even if we are able to find a solution by some other means.

k