Here is a puzzle I learned about from Bob Lord, a software entrepeneur and
puzzle fan who was grievously
injured in a 30-foot accidental fall down an abandoned mineshaft outside
Jean, Nevada on 27 October 2002.
I have a solution but have no idea if it is the best possible.
*****
There are 100 prisoners who will be placed into 100 individual jail cells.
There is no way for the prisoners to communicate, once inside. Each day, a guard
will choose one prisoner, at random, to enter a special room. In this room,
there is a light that the prisoner may turn on or off and that will remain as
the prisoner left it until the next prisoner enters, the next day. A prisoner
may tell the guard that all of the prisoners have been in this room at least
once. If he is correct, they will be released. If he is not correct, they will
all be killed. The prisoners are allowed to communicate only before they're all
locked up. How will the prisoners cooperate to guarantee their release before
they all die of old age?
The number 100 is not significant. There is no trickery involved; the puzzle
revolves entirely around the state of the light switch. Indeed, the light itself
is not significant, as long as they can tell whether the switch is in the on or
off position.
*****