lv. 100 Prisoners and a Light Bulb

Problem. $n$ prisoners; each day one is chosen uniformly at random and visits a room with a light bulb (initially off) that they may toggle. At any time a prisoner may declare that everyone has visited; if wrong, all lose. They may agree on a strategy beforehand.

Counter strategy: one prisoner is the counter. Every other prisoner turns the light on the first time they find it off (and never again); the counter turns it off whenever it is on and counts. When the count reaches $n-1$, the counter declares, and the declaration is always correct.

double bulbExpectedDays(int n) {                       // counter strategy: phases alternate "new pirate switches on" and "counter visits"
    double e = 0;
    for (int i = 0; i < n - 1; i++) e += (double)n / (n - 1 - i) + n;
    return e;
}

$n$	expected days (counter strategy)
8	about 77
100	about 10418 (28.5 years)

Proof: correctness and expected time

Correctness. Each non-counter switches the light on at most once, and only after visiting; the counter switches it off and counts each such event exactly once (the light is never turned on twice before the counter sees it, because others only turn it on when it is off). So a count of $n-1$ proves that all others visited, and the counter visited too. Time. The process alternates: with $i$ prisoners counted and the light off, wait for a new non-counter prisoner (probability $\frac{n-1-i}{n}$ per day, mean $\frac{n}{n-1-i}$), then for the counter (probability $\frac{1}{n}$, mean $n$). Summing over $i=\mathrm{0..}n-2$ gives $n{H}_{n-1}+n(n-1)$. Checked against simulation for $n=8$. Faster strategies (rounds with several counters) reduce the expected time to a few thousand days for $n=100$.