This problem was recently given to me by a friend:

One hundred prisoners are given the following challenge which if they solve will set them free. They are allowed to convene before the challenge and come up with a shared strategy. Once they decide on a strategy, the challenge starts and they will all be placed in solitary confinement with no way of communicating with each other, except that at every hour of the clock one of the prisoners will be picked at random and placed in a room with a single light and its switch, which the prisoner can either turn on or off. The light will be turned off at the beginning, before any prisoners enter the room. The goal is for one of the prisoners to know for certain that all the prisoners have visited the room with the light switch. As soon as one prisoner can deduce that with certainty, he can announce it and the prisoners win the challenge.

Now, apart from reporting this prison to the UN Human Rights Watch, can we help the prisoners come up with a strategy that will work with certainty? Take a moment or two and see if you can come up with your own solution.

One solution is to pick one prisoner to be the chosen one. The rest we will call regular prisoners. The chosen one will turn the light on every time he enters the room and the light is off, and also keep track of how many times he has turned on the light so far. Regular prisoners will turn the light off if the light is on when they enter room, but only once. Once a regular prisoner has turned the light off, he will then not switch the light ever again. Once the chosen one has turned on the light exactly 100 times he knows for sure that every single prisoner has visited. Why? Because each time a new regular prisoner enters the room with the light on, he turns the light off which then remains off until the chosen one enters the room and counts that prisoner as having entered the room. The first time the chosen one turns the light on he is essentially counting himself as having entered the room. Every time after that, he is counting a unique new regular prisoner who has entered the room.

Let's generalize and say there are $n$ prisoners instead of the constant 100 and look at a Python implementation of this experiment.

import random


light_switch = False


class Prisoner(object):
    visited = False

    def visit(self):
        self.visited = True
        return False


class RegularPrisoner(Prisoner):
    switched = False

    def visit(self):
        global light_switch
        if light_switch and not self.switched:
            light_switch = False
            self.switched = True

        return super(RegularPrisoner, self).visit()


class ChosenOne(Prisoner):
    count = 0
    prisoner_count = 0

    def __init__(self, prisoner_count):
        self.prisoner_count = prisoner_count

    def visit(self):
        # print "Chosen one visiting - ", self.count
        global light_switch
        if not light_switch:
            light_switch = True
            self.count += 1

        super(ChosenOne, self).visit()
        return self.count == self.prisoner_count


def run_experiment(n):
    global light_switch
    light_switch = False
    prisoners = [ChosenOne(n)] + \
                [RegularPrisoner() for __ in xrange(n - 1)]
    total_visits = 0
    while True:
        p = random.choice(prisoners)
        total_visits += 1
        if p.visit():
            assert False not in [r.visited for r in prisoners]
            break

    return total_visits

if __name__ == "__main__":
    experiments = 1000
    for n in xrange(1, 11):
        total = 0
        for __ in xrange(experiments):
            total += run_experiment(n)
        print "Average visits with %d prisoners over %d experiments = %f" % \
                (n, experiments, float(total) / n)

As you can see, the experiment is run 1000 time for each value of $n$ between 1 and 10. Let's look at the average number of visits for each $n$ .

Average visits with 1 prisoners over 1000 experiments = 1.000000
Average visits with 2 prisoners over 1000 experiments = 6.015000
Average visits with 3 prisoners over 1000 experiments = 13.640000
Average visits with 4 prisoners over 1000 experiments = 22.698000
Average visits with 5 prisoners over 1000 experiments = 34.929000
Average visits with 6 prisoners over 1000 experiments = 49.776000
Average visits with 7 prisoners over 1000 experiments = 66.511000
Average visits with 8 prisoners over 1000 experiments = 85.191000
Average visits with 9 prisoners over 1000 experiments = 105.357000
Average visits with 10 prisoners over 1000 experiments = 128.947000

To analyze the running time of this algorithm we need to calculate the expected number of times prisoners will be visiting the light switch room before the chosen one concludes that everyone has visited and they are all set free. Let $E(n)$ denote the expected number of visits given that there are $n$ prisoners. First, let's find a recurrence relation for $E(n)$ .

The expected number of visits before the chosen one first visits the room is $n$ since this can be seen as a Bernoulli process with $p=\frac{1}{n}$ . Once the chosen one has visited, we need a regular prisoner to enter the room and switch the light back off. The expected number of visits before a regular prisoner visits is $\frac{n}{n-1}$ . After this, the problem reduces to that with $n-1$ prisoners, except that the regular prisoner who has now visited is still in the random pool. This means on average for every $n-1$ visits of the $n-1$ prisoner problem instance, we have $n$ visits. Hence we get the following recurrence relation for $E(n)$ :

The base case of the recurrence is $E(1)=1$ . This recurrence is not linear, so most of the basic methods of solving a recurrence relation are out. Let's instead start by listing the values given by this recurrence and see if we can inductively come up with a hypothesis for a closed form. See the post on Polya's How to Solve It for more information on our inductive method here, and the post on iterators and generators if you need to learn more about generators, which are used to calculate both $E(n)$ and $H_n$ below.

>>> def E(m):
...     n = e = 1.0
...     for __ in xrange(m):
...         yield e
...         n += 1
...         e = n + n*(e+1)/(n-1)
...
>>> [e for e in E(10)]
[1.0, 6.0, 13.5, 23.333333333333332, 35.416666666666664, 49.7, 66.15, 84.74285714285715, 105.46071428571429, 128.28968253968253]

First notice that the values are very close to our average values, as expected—after all they are the expected values! An astute observer can also notice that the fractional part of the values look quite a bit like the harmonic numbers $H_n$ , at the start anyway. Let's build on this and subtract the harmonic numbers from the numbers here and see what happens. Since the similarity starts at the second number, we shift the harmonic numbers to the right by one.

>>> def harmonics(m):
...     h = n = 1.0
...     for __ in xrange(m):
...         yield h
...         n += 1.0
...         h += 1.0/n
...
>>> [e - h for (e, h) in zip(E(10), [0] + list(harmonics(10)))]
[1, 5.0, 12.0, 21.5, 33.33333333333333, 47.416666666666664, 63.7, 82.15, 102.74285714285715, 125.46071428571427]

Now we notice that the similarity to the harmonic numbers was shifted two to the right. This is characteristic of sequences involving $nH_n$ so let's instead subtract that, keeping in mind that since Python indices start at 0, we need to use n+1 in the code for $n$ :

>>> [e - (n+1)*h for (n, (e, h)) in enumerate(zip(E(10), [0] + list(harmonics(10))))]
[1, 4.0, 9.0, 16.0, 25.0, 36.0, 49.00000000000001, 64.0, 81.0, 100.0]

And there it is, we are left with $n^2$ . This gives the following hypothesis:

Proving this is a good exercise in mathematical induction which I will leave as an exercise to the reader. A hint would be to notice that the recurrence relation can be simplified to

You can then let $F(n) = n^2 + nH_n$ and prove that $F(n)$ satisfies the above recurrence relation and since $F(1)=1$ we must have $E(n)=F(n)$ for all $n\ge{1}$ .

Finally, since $H_n\in{O(\log{n})}$ the average running time of our algorithm is $O(n^2+n\log{n}) = O(n^2)$ . Let me know if you know of any better algorithms for this.