|Subject:||A hundred prisoners.|
npcomplete is now in the SF Bay Area, and i met him last night for dinner together with MarkM and MarcS. We had a long discussion about many things related to functional programming (soft type systems, identity and equality, monads), which was triggered by npcomplete's presentation of the following nice problem.
There are 100 prisoners in jail. On Day 0, all are assembled as the warden explains the rules. From Day 1 henceforth, every prisoner will be kept isolated in a separate cell. There is a room with a light switch and a light bulb. Each day, the warden will select one prisoner at random to visit the room, where the prisoner gets to observe the state of the light bulb and optionally operate the switch. Then the prisoner can choose to remain silent or to declare that all 100 prisoners have now visited the room. If the declaration is correct, all the prisoners are set free; if not, all the prisoners are shot. The prisoners are allowed to keep their own records and keep track of how many days have passed since Day 0. On Day 0, they are allowed to confer and devise whatever plan they want to get them out of prison.
Your job is to come up with a plan that will eventually allow some prisoner to make the declaration with 100% certainty (preferably sooner than later). You are guaranteed that, after any given day, each prisoner will eventually be selected an unbounded number of times.
It's interesting that we all came up with different ways of doing it. npcomplete showed us a solution that is really elegant, simple, and efficient. Hint: our technical background turned out to get in the way of finding a simple answer. You don't need any fancy equations or coding schemes to solve the problem. However, it may help to first come up with anything that works (without worrying about how inefficient or complicated it is), just to see that it's possible.
Please don't post solutions on this thread, so that people can safely discuss and clarify the problem here without spoiling it by seeing the answer. If you come up with a solution, great! Post it over here.