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