Matt Gordon posed this one to me and I found it quite tough, no fair playing if I told you the answer.
There are 23 prisoners. The warden will randomly select a prisoner each day and take them in to the room with two light switches, at least one light switch must be flipped when the prisoner enters the room. The light switches will only be changed by the prisoners (no interference from the warden). The other prisoners will have no idea who is selected each day, and are not permitted to talk to each other about who is selected. At anytime when a prisoner is taken in to the room they can say “All men have been selected”. If he’s right everyone is free to leave, if he’s wrong no one can go home and the game is over. Before the game starts the prisoners are given time to discuss and plan a way to solve the problem.
What is the minimum number of days it would require for a prisoner to say “All Men have been selected” with a 100% certainty that all 23 prisoners have been selected, explain your reasoning. Lowest answer wins.
Bonus points for who calculates the expected number of days.