Problem abstract 23 prisoners are going to be sent to isolated 23 cells and in each day, the guard will randomly pick one of them and have him change the status(either on or off) of one of two switches(switch A and B). The guard promises that if one day the prisoner he picks looks at the two switch, confidently tells that all 23 prisoners have been picked in past and it's truth, then all prisoners are set free. If the prisoner is wrong, game is over and they stay in prison for ever. Before the game begins, 23 prisoners have one chance to sit together and figure out a strategy to go free. ( Detailed version ) Quick analysis Since each prison HAS TO change one of the switch, his decision is not "which combination to change to", but "which switch to turn". Therefore his decision is only one out of two: changing switch A vs. changing switch B. The information that two switches can contribute is 2 bit a time. At any given moment, for a prisoner to tell if everyone ha...
I'm almost certain you will not find anything useful here in this blog.