$\textbf{Prisoners in Solitary Cells}$
There are $100$ prisoners locked up in solitary cells. The king gets bored and offers them a challenge. Everyday, he will randomly select and put one prisoner into a special room. (A prisoner may be selected more than once.) This special room has a light and its controlling switch. The prisoner inside the special room can turn on, turn off, or do nothing with the switch. But no other prisoner can see or control the light. On any day, the prisoners can stop this process by declaring that every one of them has been in the special room at least once. If that happens to be true, then all the prisoners will be freed. Otherwise, they will all be executed. Before starting the challenge, the prisoners are given some time to discuss. Is there a strategy to free themselves?
$\textbf{Solution}$
Yes, it is possible to get every prisoner freed. (Of course, it is possible. Otherwise, this problem will not be a brain teaser.)
$\textbf{Analysis}$
The key is to construct a count of the number of prisoners who have been put into the special room at least once. For this, the prisoner can elect one person, let's say Joe, to keep the count.
Then, every prisoner needs to signal Joe, the count, that he or she is put in the special room. However, the mechanism should be designed in such a way that
- Every prisoner should only signal once. This is because otherwise Joe will have difficulty in distinguish whether two signals are from the same person or two people.
- Only Joe can reset a signal after he has received it. No other person should reset because otherwise that signal will never be seen by Joe and is forever lost. As a result, the process will never end.
So, one possible arrangement is
- Every prisoner, other than Joe, will turn on the light if and only if he or she has never turned on the light before AND the light is currently off. If either condition is not met, this prisoner should do nothing.
- When Joe is put into the special room. If the light is on, then he increases the count by $1$ and then turns off the light. (The count is just an integer he can remember in his mind, starting from $0$.) If the light is off, then Joe does nothing.
When Joe's count reaches $99$, he can safely declare that everyone has been put into the special room at least once. (The count does not include Joe himself. Therefore, when it reaches $99$, all other prisoners are accounted for.)