You are one of P recently arrested prisoners. Thewarden, a deranged computer scientist, makes the followingannouncement:
You may meet together today and plan a strategy, butafter today you will be in isolated cells and have no communicationwith one another.
I have set up a “switch room†which contains a lightswitch, which is either on or off. The switch is not connected toanything.
Every now and then, I will select one prisoner at randomto 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 arbitrarilyoften. More precisely, for any N, eventually each of you will visitthe switch room at least N times.
At any time, any of you declare: “we have all visitedthe switch room at least once.†If the claim is correct, I will setyou free. If the claim is incorrect, I will feed all of you to thecrocodiles. Choose wisely!
Hint: not all prisoners need to do the samething.
The same warden has a different idea. He orders theprisoners to stand in line, and places red and blue hats on each oftheir heads. No prisoner knows the color of his own hat, or thecolor of any hat behind him, but he can see the hats of theprisoners in front. The warden starts at the back of the line andasks each prisoner to guess the color of his own hat. The prisonercan answer only “red†or “blue.†If he gives the wrong answer, heis fed to the crocodiles. If he answers correctly, he is freed.Each prisoner can hear the answer of the prisoners behind him, butcannot tell whether that prisoner was correct.
The prisoners are allowed to consult and agree on astrategy beforehand (while the warden listens in) but after beinglined up, they cannot communicate any other way besides theiranswer of “red†or “blue.â€
Devise a strategy that allows at least P - 1 of Pprisoners to be freed.
