Question

You are one of P recently arrested prisoners. The warden, a deranged computer scientist, makes the following announcement:

You may meet together today and plan a strategy, but after today you will be in isolated cells and have no communication with one another.

I have set up a “switch room” which contains a light switch, which is either on or off. The switch is not connected to anything.

Every now and then, I will select one prisoner at random to enter the “switch room.” This prisoner may throw the switch (from on to off, or vice-versa), or may leave the switch unchanged. Nobody else will ever enter this room.

Each prisoner will visit the switch room arbitrarily often. More precisely, for any N, eventually each of you will visit the switch room at least N times.

At any time, any of you declare: “we have all visited the switch room at least once.” If the claim is correct, I will set you free. If the claim is incorrect, I will feed all of you to the crocodiles. Choose wisely!

• Devise a winning strategy when you know that the initial state of the switch is off.

• Devise a winning strategy when you do not know whether the initial state of the switch is on or off.

Hint: not all prisoners need to do the same thing.

The same warden has a different idea. He orders the prisoners to stand in line, and places red and blue hats on each of their heads. No prisoner knows the color of his own hat, or the color of any hat behind him, but he can see the hats of the prisoners in front. The warden starts at the back of the line and asks each prisoner to guess the color of his own hat. The prisoner can answer only “red” or “blue.” If he gives the wrong answer, he is fed to the crocodiles. If he answers correctly, he is freed. Each prisoner can hear the answer of the prisoners behind him, but cannot tell whether that prisoner was correct.

The prisoners are allowed to consult and agree on a strategy beforehand (while the warden listens in) but after being lined up, they cannot communicate any other way besides their answer of “red” or “blue.”

Devise a strategy that allows at least P - 1 of P prisoners to be freed.

Answer 1

Here is the solution. Please do upvote thank you.

1. All the prisoners plan together and select one of them to declare that all the prisoners had visited the room.
2. Let us assume that the nominated prisoner maintains the count of all the prisoners that entered the room. Let the count be 1 initially.
case-1 : when the switch is initially off -
a. when the nominated prisoner enters the switch room:
1.If the switch is on, he turns it off and increases the count. If the count becomes P-1 then he declares that
every prisoner have visited the room.
2.If the switch is off, he does nothing.
b.If any other prisoner except the nominated prisoner enters the room,
1. If he sees that the first time switch is off, he will turn it on.
2.else he does nothing.
case-2:when we dont know whether the switch is on/off-
a.when the nominated prisoner enters the room:
1.If the switch is on, he turns it off and he increases the count. If the count becomes 2P-2 he will declare that all the prisoners have visited the switch room.
2.else he does nothing.
b.If any other prisoner except the nominated prisoner enters the room,
1. If he sees first two times that the switch is off, he will turn it on.
2.else he does nothing.