100 prisoners and a lightbulb 100 prisoners are imprisoned in solitary cells. Each cell is windowless and soundproof. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his or her own cell. Each day, the warden picks a prisoner equally at random, and that prisoner visits the central living room; at the end of the day the prisoner is returned to his cell. While in the living room, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room), all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world can always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.
Before this whole procedure begins, the prisoners are allowed to get together in the courtyard to discuss a plan. What is the optimal plan they can agree on, so that eventually, someone will make a correct assertion?
http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml
I was wondering does anyone know the solution for the 4,000 days solution. Also, anyone got any ideas on how to solve this? 
Just wanted to know if anyone got any ideas how to solve this. http://www.siam.org/ is offering prize money for a proof of a optimal solution for it. I suppose to make it clear the people want a plan that would mean on average it would take least amount of time to free the prisoner. The point is the average run time is as low as possible. 
 A: 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.
A: 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.
A: 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.
A: 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.
A: 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 ...
A: A random person chosen could mean that all $100$ prisoners will never all be chosen in their lifetime so it seems to me that there is no minimum amount of time to satisfy the "$100$% certain" situation (in the general case) so what is the point of this question?  It may take anywhere from $100$ days to a lifetime.  Why don't they just each get a number assigned to them from $1$ to $100$ and make a mark in the living room when they are in it?  Prisoners are good at that type of stuff.  Perhaps scratch a binary (stick men) code?
Also, what happens if one of the unchosen ones dies before all $100$ are chosen? How is it verified if all the prisoners have visited the living room or not? If it is written down somewhere then maybe the prisoners should find out where and use that info.
Too many unknowns in this badly worded question to come up with a reasonable answer.
A: My solution to this was a more generalised version of the above.  At any given time, each prisoner has a value.  This starts at 1 for all prisoners except one of them that has a value of 29.
On each night the light bulb has a power of two value that is agreed by the prisoners at the beginning.  When a prisoner enters the room (on any day except day one), if the light is on they increase their value by the light-bulb value of the night before.
They then expand their value in binary.  If they have a 1 in the power-of-two slot for the value on the subsequent night, they ensure the light is left on and subtract this from their own value.  If they have a zero in that slot they ensure the light is left off.
The sequencing of light bulb values is chosen by drawing from a random distribution that reflects the expected density of the powers-of-two values present in the prisoner population as a whole given the previous choices.  (The prisoners have to have prodigious memories for this algorithm).
If any prisoner finds themselves worth 128, they announce success.
