This is an old but difficult one. Since it mentions light switches I thought I'd post it here.
23 CPF members are sent to prison for excessive flashaholism. On the first day of the sentence, the warden gathers them all in a big room and explains the prison rules:
1) The prisoners will be allowed have a strategy planning discussion here in the big room today. After that session, they will all be put in separate solitary confinement cells and no further communication will be possible.
2) The prison has a special room called the "switch room", which has two light switches (not connected to anything), labelled "A" and "B". Each switch can be either "on" or "off". The warden will not tell you the initial state of the switches.
3) From time to time the warden will select one of the prisoners and take him to the switch room. The prisoner must select exactly one of the two switches and flip it. The prisoner then gets taken back to his cell.
4) The warden can choose prisoners to take to the switch room any way he likes, but every prisoner will eventually be taken to the switch room infinitely often (i.e. no matter how many times you've been taken to the switch room, you'll eventually be taken again). Also, nobody except these 23 prisoners gets to touch the switches.
5) At any time, any prisoner can tell the warden "we have all been to the switch room". If the statement is correct, the prisoners are all given new flashlights and set free. If the statement is incorrect (someone has not yet been to the switch room) the prisoners are all locked up for life with no possibility of ever leaving. Obviously no prisoner should make the announcement unless he's absolutely sure it's correct.
What strategy can the 23 prisoners settle on during the initial meeting, to guarantee that they're eventually set free?
23 CPF members are sent to prison for excessive flashaholism. On the first day of the sentence, the warden gathers them all in a big room and explains the prison rules:
1) The prisoners will be allowed have a strategy planning discussion here in the big room today. After that session, they will all be put in separate solitary confinement cells and no further communication will be possible.
2) The prison has a special room called the "switch room", which has two light switches (not connected to anything), labelled "A" and "B". Each switch can be either "on" or "off". The warden will not tell you the initial state of the switches.
3) From time to time the warden will select one of the prisoners and take him to the switch room. The prisoner must select exactly one of the two switches and flip it. The prisoner then gets taken back to his cell.
4) The warden can choose prisoners to take to the switch room any way he likes, but every prisoner will eventually be taken to the switch room infinitely often (i.e. no matter how many times you've been taken to the switch room, you'll eventually be taken again). Also, nobody except these 23 prisoners gets to touch the switches.
5) At any time, any prisoner can tell the warden "we have all been to the switch room". If the statement is correct, the prisoners are all given new flashlights and set free. If the statement is incorrect (someone has not yet been to the switch room) the prisoners are all locked up for life with no possibility of ever leaving. Obviously no prisoner should make the announcement unless he's absolutely sure it's correct.
What strategy can the 23 prisoners settle on during the initial meeting, to guarantee that they're eventually set free?