100 prisoners and a lightbulb
Solution 1:
The "standard" solution for the puzzle is the following. Prisoners choose one of them, lets call him "The Counter". The job of The Counter is to count the prisoners who have been in living room. Other prisoners' job is to give a signal to The Counter that they have been in the living room. This is done as follows. The Counter is the only person who can turn the light off. Others can only turn the light on and do it only once. That is if a prisoner walks into the living and the light bulb is off and he has never turned the bulb on, then he turns it on. The bulb will stay on, until The Counter comes and turns it off. When The Counter has turned the bulb off 99 times, he knows all prisoners have been in the living room.
I don't know what is efficiency of this solution, but in your link it is stated that the standard solution takes 27-28 years on average. So I suspect that is efficiency of this solution.
Solution 2:
Here's one way to improve on Levon's solution. I don't have time to do a full probability analysis just now, but my very rough estimates suggest that with careful tuning, techniques like this should be able to get the average running time down to around 4000 days:
It's not certain but "pretty likely" that every prisoner gets to visit the living room at least once during the first, say 800 days. So divide the strategy into several phases:
Day 1 to 800: Everyone toggles the lamp the first time they see the living room. If we're lucky, after day 800 there will be 50 prisoners who have ever turned off the lamp. They are the "active" prisoners. (If we're unlucky and there's someone who hasn't been in the living room yet, there will be less than 50 active prisoners).
Day 801 to 1600: Ever prisoner who is active after the first phase toggles the lamp the first time they see the living room during this period. (The prisoner who enters on day 801 makes sure the lamp is already off before he does his part -- if so, something will have gone wrong but proceed according to plan anyway). The prisoners who turned the lamp off during this phase are still active. If we're lucky there are 25 off them.
Day 1601 to 2400: Halve the number of active prisones once again. This time those who turned the lamp on stay active; there are now 13 active prisoners unless something went wrong.
Day 2401 to 6000: Count the 13 still active prisoners using the standard algorithm, with a Counter selected in advance.
If anybody finds themselves still in prison on day 6001, everyone shrugs and starts the entire algorithm over from day 1. Since 3600 days should be plenty of time to count 13 active prisoners, the main risk is that someone who needed to didn't get to participate in one of the first three phases, and since the risk of that is small, it won't affect the expected running time of the algorithm much.
With the parameters given here (and several approximation shortcuts in the calculation) this strategy has an average running time of 4353 days. But there's room for some optimizations by tweaking the numbers. It appears that 800 days is close to optimal for the first halving, but the later halvings can be shortened a bit without incurring quite as large a total risk of missing an active prisoner and having to restart.
EDIT: After a semi-systematic search for better parameters it seems that the best this method can get is an average running time of 4227 days (about 11½ years), which is achieved by three halving phases of 840, 770 and 700 days, followed by a counting phase of 2200 days. Neither more halving phases nor fewer ones improved the overall efficiency. Back to the drawing board ...
Solution 3:
A survey of various strategies can be found at https://www.math.washington.edu/~morrow/336_11/papers/yisong.pdf. It describes a strategy ("two-stage counting") which is believed, based on simulations, to yield expected run times between 3500 and 4000 days, and references a hybrid strategy by a Bertram Felgenhauer which is supposedly proved to run in 3949 days average.
Solution 4:
The shortest time solutions that I am aware of are based on this scheme, first suggested by Paul Hammond here.
Time is broken into Rounds, and each round is further broken into two Stages. In Paul Hammond's original scheme, the first stage in each round is 2600 days, while the second is 2700 days.
Each prisoner is considered to start with a virtual "token". If the light is off, they can leave their token in the room by turning the light on (so they no longer have a token themselves). They can pick up a token left in the room by turning the light off. At the initial meeting, A head counter and 9 assistant counters are picked. Everyone else is a "drone". Drones never pick up a token (except on the last day of a stage). They can only leave one.
During the first stage, the drones leave their token in the room when the light is off. If the light is on, or they have already given away their token, they do nothing. All counters pick up any tokens left in the room until they have 10 tokens (including their own). After that, they do nothing in this stage. On the last day of the stage, whoever visits the room picks up any token that was there (if this was a drone, and he had not yet given his own token away, then he will have two tokens to pass on in the next round, which he must do one at a time).
During the 2nd stage, tokens are passed 10 at a time from assistant counters to the head counter. Drones never turn the light on or off. Asssistant counters can only turn on the light if they have 10 tokens to pass. After passing, they become drones. The head counter turns the light off on his next visit, and adds 10 tokens to his inventory. If he has all 100 tokens, he declares everyone has visited. As with the first stage, if the light is on on the last day of the stage, the visitor picks up the 10 tokens there, and saves them for stage 2 of the next round, when he will act as an assistant counter.
If the round is unsuccessful, an additional round with new stage 1 and stage 2 take place, and so on, until the head counter finally reaches 100.
Paul Hammond originally had them start over with each new round (everyone gets their tokens back and all counters reset their counts to just their own token). Computer simulations estimate the expected run time at 3964 days. AlexH suggested saving the tokens as I described above. This change and tweaking of stage lengths (which need not be the same between rounds) produced a claimed estimated expected run time of 3600 days. However, the person posting that result did not say what stage lengths he used. However a later variant of the scheme which picks the counters during a special 40 day period at the start and uses initial stage lengths of 2000 and 1500, while all later stages are 300 days each, results in an estimated expected run time of 3489 days.
A later scheme appears to have dropped that under 3400 days, but I have not yet examined that scheme.
Solution 5:
The halving strategy seems to work well - that is in a frrst phase of x1 days everyone toggles the lamp on first entry (lamp is always turned off on the last day of a phase). On the next phase i+1 everyone that toggled the lamp to a certain state in phase i, continue. This certain state depends on the number of players in phase i - if it was even (as initially - 100), then everyone who turned off the lamp continue for i+1, if it was odd - then everyone that turned it on - this is to ensure noone "slipping". This should continue until there is a phase with 2 players. Then the if one of the two enters and sees the lamp on, he knows that he is second, and in retrospect that in each previous phase all the active players managed to enter the room, including the first phase, so everyone has been at least once there.
The phases are with 100, 50, 25, 13, 7, 4, and 2 players, so if we try to solve the following minimization problem - minimize the sum of the phase lengths, with the constraint that the total probability of all phase players go into the rooms at least once on each phase is exactly (or at least - depending on what minimization algorithm is used) 0.5. Of course, a different target probability can be set.
There are two approaches: 1. solve a constrained problem where objective is total days, and constraint is total probability = 0.5 (or something else). 2. solve unconstrained problem where the objective function somehow includes total length and target probability (this allows greater variety of methods).
In all cases there is a general problem that the actual domain is integers and minimizing functions over integers is hard to do, so at least I defaulted to approximations. Additionally it seems that the constrained task is hard and the unconstrained task is nonconvex.
For Nelder-Mead and somewhat contrived target function I get different solutions (all very close to p=0.5) depending on starting point. The minimum, achieved from a sane starting point is around 3439 days. (See below for sane starting point).
SLSQP and COBYLA seem to behave more consistently once some numerical problems are resolved (both in objective function and constraint) and give 3455.
Regarding sane initial guess - it seems reasonable to guess that if target probability is 0.5. then we can pick initial phase lengths so that all phase probabilities are equal - to 0.5^(1/7). Experimentation confirmed that this may be a good initial guess.