Twist on the popular prisoner lightbulb riddle.

I honestly can't tell anymore what your concerns are so I don't have any way to answer you. You have what seems to me like a vastly overcomplicated understanding of the puzzle. Will you be satisfied if I showed you a working strategy for the prisoners in the case where there are just 3? (I took the idea from a post elsewhere in here.)

Consider the following strategy: the prisoner that gets called to the room on the first day does nothing, and will never do anything. The other two prisoners flip the switch exactly once, on the first day they get called. Here is how a prisoner knows whether all 3 prisoners have been to the room: for the first prisoner, he will know everyone has been to the room after two things happen: (i) there is a day where he isn't the one to be called to the room, and (ii) after that day he is called to the room and sees the switch on mode OFF. This is because in order for this to happen, the bulb must have necessarily been flipped twice, so the two other prisoners where in the room.

The second and third prisoners will know everyone has been to the room, once they get called into the room and the bulb is OFF at least twice in a row. This is because they know the 1st prisoner has been into the room on the 1st day, and they know that in order for the bulb to be OFF twice in a row, both of them must have visited the room.

Here is how to show that this strategy works given the restrictions on the Warden. Consider any possible legal strategy M1 used by the Warden. Quoting the OP, we have that:

(1) For any sequence of inputs a_0, a_1, ..., where a_0 represents the input on the first day, a_1 represents the input on the second day assuming input a_0 on the first day, and so on, the output of M1 contains every prisoner infinitely often.

(2) The output of the machine is of the form "Send prisoner x into the room" where 1 <= x <= 100. (In particular, the machine halts for every input).

We know that there are days, t_2 and t_3, where prisoners two and three visit the cell for the first time (for prisoner 1 we have t_1=1). This is because if these days did not exist, then it would imply that there is some sequence of puzzle inputs where a certain prisoner never gets called into the room, contradicting (1). Now take T=max{t_2,t_3}+1. We know that there are times t_1' > T, t_2' > T, t_3' > T where prisoners one, two and three will be called again into the room with the cell, by (1). On those times each of the prisoners will learn that everyone else has visited the room. Thus taking max{t_1',t_2',t_3'}, we have that the prisoners will win in finite time.

As for proving the negative statement (perhaps the Warden can win if there are 100 prisoners): I don't know how to do it, since I haven't solved the puzzle myself, but this doesn't mean the problem is ill-defined.

/r/math Thread Parent