100 people are being held prisoner in a jail. They are told that in one hour, they will all be taken to separate windowless, soundproof cells. One at a time, and in a random order, they will be taken from their cells, interrogated, and then sent back to their cells. All interrogations will take place in the same room, which contains one light bulb and the switch that operates it. The light is initially off, but the inmates are free to toggle the switch as often as they want, whenever they are in the interrogation room, and the prison guards will not toggle the switch at all. No prisoner can see the light from their cell. Only one prisoner is interrogated at a time, each prisoner can be interrogated multiple times, and they have no way of communicating besides the light switch. The length and amount of time between interrogations is random, so no help there.
At any time, any prisoner under interrogation may state, "Everyone has been interrogated at least once." If this statement is true, everyone will be released. If it is false, all of the prisoners will be executed.
The prisoners have one hour to work out their strategy before they're isolated for good. How do they get released?
Note: The selection process for interrogations is random and fair; some prisoners may be interviewed multiple times before another prisoner is interrogated at all, and after any point in time, every prisoner will be interrogated an infinite number of times more.
My proposed solution is
rot13 behind the fold.
Qrfvtangr bar cevfbare nf 'gur ibvpr'. Gur svefg gvzr n cevfbare jub vf ABG gur ibvpr ragref gur ebbz naq gur yvtug vf bss, ur jvyy ghea vg ba. Nyy bgure gvzrf, nalbar jub vf abg gur ibvpr jvyy yrnir gur yvtug nybar. Rnpu gvzr gur ibvpr ragref gur ebbz naq gur yvtug fjvgpu vf ba, ur jvyy ghea vg bss naq vaperzrag uvf pbhag ol bar. Bapr ur unf ernpurq n pbhag bs 99, ur jvyy naabhapr gung nyy cevfbaref unir orra vagreebtngrq.
For bonus points, what is their strategy if they don't know the initial state of the light switch?
Alternative: suppose there is one interrogation per day. In this case there exist different more efficient solutions.
I didn't try to solve either of those.
More puzzles
here.
