There are 100 prisoners locked up in solitary cells. There is a central living room with one light bulb; the light bulb is initially off. No prisoner can see the light bulb from his cell. Every day, the warden picks a prisoner at random (i.e., the warden may pick one prisoner multiple days in a row), and that prisoner is taken to the living room. In the room, the prisoner can do one of three things: 1) toggle the light switch, 2) do nothing, or, 3) assert that all 100 prisoners have been in the living room at least once. If this assertion is false, all 100 prisoners are shot. If it is true, they go free. Before they were locked up, they got an hour to discuss a plan. What should be their strategy? [There are at least three known solutions, only one of which will get them out within their lifetime. Try to estimate the runtime of your solution.]
Progression, not hint:135