10 prisoners are locked up in individual cells, unable to see, speak or communicate in any way with each other. There is a exercise room with a single light, that is initially off and the prisoners cannot see the light from their own cell.
Every day, the warden picks a prisoner at random, and that prisoner goes to the exercise room.
While there, the prisoner can choose to switch the light on or off, and are not allowed to leave a message.
At any point, any prisoner can claim that all 10 prisoners have been to the exercise room. If they are wrong then all 10 prisoners will be locked up forever! However, if they are correct all of the prisoners are set free.
Before the random picking begins, the prisoners are allowed to discuss a plan. What is their best plan to determine when all 10 prisoners have visited the exercise room?
One person is chosen as a Counter and will only ever turn the light off, and they will count the number of times they do this.
Each of the other prisoners will only turn the light on once. They will only touch the light if it's already off - and only if they've not yet turned it on.
Ever time the Counter goes to the exercise room, if the light is on again, they'll know a new person has entered the room, and they'll turn the light off.
Once the Counter has turned the light off 9 times, they will know that the other 9 prisoners have entered the room, and therefore can ask for everyone to be released.
For 10 prisoners, on average, this would take around 91 days.
For 20 prisoners, on average, this would take around 381 days.
For 50 prisoners, on average, this would take over 6 years.
For 100 prisoners, on average, this would take over 27 years.