A few weeks ago a colleague of mine proposed me an interesting problem which years ago he found very challenging and a lot of fun and of course you can’t just tell this kind of thing to a computer scientist and expect no reaction whatsoever, so I went ahead and started thinking of a solution. The first thing to say about this problem is that it can have more than one solution and that the only way to compare them is by calculating the average time it would take for the problem to be solved following that particular approach. The goal of this post is not to do a mathematical examination of all the possible solutions but only to talk about the solution I came up with, leaving the problem open to the readers imagination. If you come up with more solutions, please don’t hesitate to comment about them!  The problem statement is the following:

There is a prison with 100 prisoners isolated from each other and a very bored prison warden who proposes a challenge: each day he will select a prisoner at random and put him in a special room fitted with nothing more than a lamp and he will give that particular prisoner the opportunity to tell him when all of the prisoners have been at least once in that room. If the prisoner is right all of them would be given a pardon and if he is wrong all of them die. Since the prisoners are isolated, he will give them one hour to elaborate a plan between them, after which they won’t be able to communicate again until the game is over.

At first glance, it’s obvious that the only link between each prisoner in the room and the next one is the lamp, so it has to be used as a method for communicating the next prisoner some message. Defining the lamp as a method to convey a message seems trivial, but given that it can only hold one bit of information it seems that we need something more in order for this message to have a meaning, we will call this extra information the context of the message.

Now, the main difficulty of the problem is defining a context with which to assign a meaning to the message, or rather define how the prisoner going into the room will interpret the lamp being on or off. One way to look at it is that we need something to accumulate information so that whenever a prisoner goes into the room he has a bigger picture than just one bit, I propose this accumulator to be another prisoner which will interpret the message left in the room and accumulate the information, thus acting like an 100 bit message himself.

Given that one of our prisoners is an 100 bit accumulator, who does this job has to be decided during the planning hour, and also how and what the other prisoners should convey through the lamp. For this particular approach, each of the other prisoners will have to inform the accumulator if they have been in the room or not by turning the lamp on, but they will only do so if when they entered the room the lamp was off and if it’s the first time they’ve been there, this way the lamp will inform the accumulator that at least one of the other prisoners has been there for the first time. Finally, the accumulator has to turn off the lamp every time he goes into the room and finds it on, so that a new cycle can start.

With this solution, the accumulator prisoner (or counter as I called it in the following code) will have to go at least 99 times to the room to be able to tell the warden with complete certainty that all of the prisoners have already been there. Considering the best case, this would take him as least as 198 days if he went after each prisoner and for every prisoner this was the first time. If we assume now that on every 100 day cycle at least one new prisoner has been into the prison and that the accumulator is always the last, it would take him 9900 days which is quite a bad prospect for the prisoners and probably most of them will be already out by then.

The following code attempts to simulate the situation by creating random numbers as if it was the warden picking a random prisoner, it also includes the solution by having the accumulator (counter) prisoner and a lookup table for each of the prisoners (in order to store if they have  been in or not).

int main()
{
    // ID of the prisoner in charge of counting
    const int prisoner_counter_id = 0;
    // Prisoner state (been with lamp off or not)
    int prisoner_lookup[100];
    // Number of counts by prisoner in charge of counting
    int prisoner_counter = 0;
    // State of the lamp
    int lamp = 0;
    // Current prisoner in the room
    int prisoner_room;

    memset(prisoner_lookup, 0, 100*sizeof(int));

    while (prisoner_counter < 99)
    {
        // Select a random prisoner
        prisoner_room = rand() % 100;

        if (prisoner_room == prisoner_counter_id)
        {
            // Random prisoner is the counter
            // If the lamp is on, count it
            prisoner_counter += lamp;
            // Turn off the lamp
            lamp = 0;
        }
        else if ((lamp == 0) && (prisoner_lookup[prisoner_room] == 0))
        {
            // If the lamp is off and prisoners "first time"
            // Turns on the lamp
            lamp = 1;
            // He has now completed his visit to the room
            prisoner_lookup[prisoner_room] = 1;
        }
    }
    
    printf("Counter counts %d\n", prisoner_counter + 1);

    return 0;
}

As I said, there are other solutions to this problem although it seems a bit difficult to come up with them once you already have a solution. I suggest you give it a try and see what you can get. If you still can’t find any other solutions, I’m sure a fast search will give you many results, but what would be the challenge in that?

Lamp Image  |