A while ago I rediscovered a riddle that had fascinated me a few years back, and it took hold of me yet again.

Reminiscent of chess problems, the conditions for this riddle are very simple, but finding a solution is not. Actually, since there is no proven optimal solution known, it's really more of a problem than a riddle.

The problem

Imagine a prison where 100 prisoners are kept in soundproofed cells without windows. The prison has only one guard. At the start of their imprisonment, the prisoners are allowed to meet in a central courtyard once. This will be the only time they see eachother during their imprisonment. Each day the guard will randomly pick one prisoner and take him to a secret room. The room is completely empty save a light switch and a lightbulb. The lightbulb is not reachable by the prisoner. The prisoner may then choose to turn on the light, turn off the light, or leave it at its current state. Before leaving the room, the prisoner may state that all 100 prisoners have been to the secret room. If his claim is true, all prisoners are set free. If he is wrong, all of them will be decapitated.

It's apparent that the difficulty of this problem lies in the fact that the prisoners can only send one bit of data at a time, and that the receivers and senders of that data have no way of directly identifying eachother. Still, it's possible for them to think up some sort of system that lets them communicate and identify eachother.

If you want to figure out a solution yourself, refrain from reading the following section just yet.

***

Most obvious solution: The single counter.

This solution is fairly straightforward, and is unfortunately also the only one I managed to come up with myself.

During the meeting in the courtyard the prisoners elect one of them to be the 'counter'. The rules from then on are simple: The light is off by default. When a prisoner enters the secret room for the first time with the light being off, he turns it on. If the light is already on, he leaves it so. When the counter visits the room and finds the light turned on, he will turn it off again. When he has done this 99 times, he can be absolutely certain that all prisoners have been to the room (Unless one of them has been stupid enough to mess up the system). Unfortunately, chances of the counter getting picked by the guard at convenient times are very slim since the prisoners are picked by random. In his paper, Berkeley PhD. student William Wu calculates the average running time of this solution to be about 28 years.

An optimization of this solution involves letting the counter be assigned dynamically. This requires a 100-day selection stage before regular counting takes place. During these first 100 days, all prisoners will leave the light off, until one of them enters the room for the second time and turns the light on. He will then know that all prisoners before him have been unique and this will shorten the cycle considerately. The person to enter the room on day 100 will then have to turn the light off again, or, on the off chance (p=100-100 ) that no one has entered the room twice, state that all prisoners have been in the room. On day 101, counting proceeds as with the predetermined counter. This alteration shortens the average running time by roughly 4 years.

Complete Cycle System

This method is almost certainly the least efficient one. The idea is that each 100 days, the first prisoner to enter the room turns the light off. During the next 99 days, only prisoners that have already visited the room during that particular 100 day cycle can turn the light on. If the prisoner that enters the room on day 100 finds the light off, and hasn't been to the room before himself, he may claim freedom. Even though the cycles can have an overlap of one day, the time it takes on average to succesfully complete this solution is 1.0608 x 1044 years. (current estimated age of the universe: 13.73 x 109 years)

Distribution System

In this system prisoners are numbered 1 through 100. Just like the previous solution, 100-day cycles are used. When a prisoner enters the room on day N and N is also the number given to him, he turns the lamp on. The following prisoner to enter the room then knows that prisoner N has visited. During later cycles, he will then also turn on the lamp on that day if he happens to visit it, to pass the information to other prisoners. When any prisoner knows all prisoners have visited, he claims freedom. This solution takes around 8300 years.

Drones, counters and a master counter

The single-counter strategy takes such a long time because there is only one person doing all the counting. Obviously solutions employing multiple counters are far more effective because the odds of a counter being picked are higher. However, having multiple counters means there has to be some way those counters can communicate what they have counted. This is achieved by having multiple phases during the counting process: in phase A, all helper-counters and the master counter count new prisoners up to a certain quotum, and in phase B, the master counter counts the number of helper-counters that have made their quotum. If all have succeeded, freedom can be claimed. If not, phase A and B both have to be repeated in increasingly shorter durations until all prisoners are counted. In these solutions it's possible to assign counters dynamically similar to the optimization in the single-counter approach. Most importantly, all paramaters such as the number of counters, the size of the quotas and the lengths of the phases can be adjusted to obtain an optimal average running time.

Multiple stages and Binary tokens

Being the optimal approach so far, these solutions have multiple dynamic counters and multiple levels of stages. In each stage tokens are passed and every prisoner starts the whole ordeal with a token of 1. Every stage the tokens become bigger and counters either drop their token (by turning the light on) when the light is off, or pick up a token when the light is on (by turning the light off). If not all tokens are counted by one person in the last stage, all stages are repeated until all tokens are passed to one person. It makes sense to increasing the sizes of tokens by factors of two, so that two smaller tokens in stage N can be combined to be one token in stage N+1. If this binary approach is used, it is convenient to have one prisoner start with an additional token of 28 (broken up into 16, 8 and 4) so that the token count in the top stage will amount to 128. Using this approach, users from Wu's forum have been able to bring down the average running time to 3460 days, which stands as the lowest to this day. It is thought an optimization could be possible by letting observing, non-counting prisoners remember which tokens they see during the various cycles. (e.g.: a prisoner sees a 64 token in cycle 1, then a 32-token in the next, then a 16-token in the next, etc.)

Taking a gamble

It's not certain whether an optimal solution will ever be proven for this problem, but then again, in real life, the smartest thing the prisoners could do is just wait about 5 years and then claim that everyone has been in the room, as this will be true 99.999% of the time. So if you find yourself in this situation, just wait it out.

If you liked this problem, here are similar problems.

References:

The paper by William Wu: http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf

Forum discussion on his site: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027805293 - The solutions above have been concocted by the bright minds on this forum.

Forum discussion on physicsforum.org: http://www.physicsforums.com/archive/index.php/t-30021.html