101 Prisoners and 2 Lightbulbs

Hello everyone, recently I discovered this puzzle and it’s too challenging for me I couldn’t solve it. If anyone knows the answer, I would really appreciate it if you can help me out here, thank you.

The puzzle :

You and another 100 prisoners are being locked up by a tricky warden. One day the warden comes to you and say: “I will give you a challenge, if you can pass the challenge then all 101 prisoners will be set free. There is a room which has 2 lightbulbs, one is yellow and one is green. Each lightbulb is controlled by an independent switch, so a prisoner can toggle whichever lightbulb they want on or off.

Everyday I will call up one of the 100 prisoners randomly into the room and let him toggle the switches. To ensure fairness, I will use a random number generator to call up the prisoner, but it doesn’t guarantee every prisoner will visit the room an equal number of times. And I will continue to do this everyday forever, for as long as it takes for them to solve my puzzle.

I won’t call you into the room, no. Your task is to devise a strategy for those 100 prisoners to follow. You must write it down onto a piece of paper and I will print 100 copies of it and give every prisoner a copy. So everyone must follow an exact same strategy with no variation whatsoever. That means you cannot elect a specific person to count the lightbulb, or give different instructions to different prisoners. Also, the prisoners cannot communicate with each other in any way.

At any time, a prisoner can declare that all 100 prisoners have already visited the room. And if he’s right, all of you will go free, but if he’s wrong, I will execute you all. What strategy can you devise to guarantee the freedom of all prisoners?

guest
0 Comments
Newest
Oldest
Inline Feedbacks
View All Comments