Fifty prisoners are to be freed if one of them correctly announces that all 50 have visited a certain room. The room has a light switch (the light starts off). Prisoners are taken to the room one at a time, in an order chosen uniformly at random each time (a prisoner may visit many times, another may never be picked for a long while). They cannot communicate except through the light, and may meet beforehand to agree a plan.
Under the standard plan, one prisoner is designated the counter. Any other prisoner who enters the room finding the light off and who has not yet done so turns it on, exactly once in his life; otherwise he leaves it alone. Only the counter turns the light off, and he does so each time he finds it on. At what count of switch-offs can the counter safely announce that everyone has visited? (Give the number of times he must have turned the light off.)
Related Problems