Index ¦ Archives ¦ Atom

One hundred prisoners and a light bulb simulation

This is a little off my usual topic of IT Security but it's something I've been thinking about a bit lately. I recently came across the "One hundred prisoners and a light bulb" riddle. It was posed as:

A group of 100 prisoners, all together in the prison dining area, are told that they will be all put in isolation cells and then will be interrogated one by one in a room containing a light with an on/off switch. The prisoners may communicate with one another by toggling the light-switch (and that is the only way in which they can communicate). The light is initially switched off. There is no fixed order of interrogation, or interval between interrogations, and the same prisoner will be interrogated again at any stage. When interrogated, a prisoner can either do nothing, or toggle the light-switch, or announce that all prisoners have been interrogated. If that announcement is true, the prisoners will (all) be set free, but if it is false, they will all be executed. While still in the dining room, and before the prisoners go to their isolation cells (forever), can the prisoners agree on a protocol that will set them free?

I think there are several version that all run along the same lines but with slightly tweaked wording.

The general solution to the puzzle is that;

  • All the prisoners decied to elect one prisoner as the leader.
  • When a prisoner is interrogated if the light is off and they have not switched it on before they will switch the light on. Otherwise they will leave the light unchanged.
  • Only the leader can switch the light off. After the leaer has switched the light off 99 times they know all other prisoners must have been interrogated.

This works and from a logic point of view is fairly elegant. However it seemed inefficient to me. I wanted to know how many interrogations before the prisoners are set free. I feel sure there is some mathematical way you could calculate the average but that's beyond me so I kidnaped 100 people and locked them in my basement wrote a Python script to simulate the problem.

#!/usr/bin/python3
# -*- coding: UTF-8 -*-
"""
A group of 100 prisoners, all together in the prison dining area, are told that
they will be all put in isolation cells and then will be interrogated one by
one in a room containing a light with an on/off switch. The prisoners may
communicate with one another by toggling the light-switch (and that is the
only way in which they can communicate). The light is initially switched off.

There is no fixed order of interrogation, or interval between interrogations,
and the same prisoner will be interrogated again at any stage. When
interrogated, a prisoner can either do nothing, or toggle the light-switch,
or announce that all prisoners have been interrogated. If that announcement is
true, the prisoners will (all) be set free, but if it is false, they will all
be executed.

While still in the dining room, and before the prisoners go to their isolation
cells (forever), can the prisoners agree on a protocol that will set them free?
"""
import random

light_bulb_on = False


class Prisoner():
    """The basic class there should be 100 of these"""

    def __init__(self):
        """Sets up the initial variables"""
        self.has_switched_on_light_bulb = False

    def interigation(self):
        """
        When the prisoner goes into the room, if the light is on they leave it
        otherwise if it's off and they have not yet switched it on they turn
        the light bulb on
        """
        global light_bulb_on

        if self.has_switched_on_light_bulb is False and light_bulb_on is False:
            light_bulb_on = True
            self.has_switched_on_light_bulb = True


class Leader(Prisoner):
    """
    Only the leader can switch the light bulb off. After they have swtiched the
    light bulb off 99 times, they know all prisoners have been interrogated.
    """

    def __init__(self):
        """Sets up the initial variables"""
        Prisoner.__init__(self)
        self.switch_off_count = 0

    def interigation(self, ):
        """
        When the leader gets in interrogated they can switch the light off
        """
        global light_bulb_on

        if light_bulb_on:
            light_bulb_on = False
            self.switch_off_count += 1

        if self.switch_off_count == 99:
            return "All prisoners have been interrogated"


def run_simulation():
    """
    Runs a simulation of the onehundred prisoners and a light bulb problem and
    returns the number of interigations before the prisoners are released.
    """
    # Add one leader and 99 prisoners
    number_of_interigations = 0
    responce = None

    prisoners = [Leader()]

    for _ in range(99):
        prisoners.append(Prisoner())

    while responce != "All prisoners have been interrogated":
        responce = random.choice(prisoners).interigation()
        number_of_interigations += 1

    return number_of_interigations


# Run the simulation 1000 times and print out the average number of
# interigations before the prisoners are released.
average = 0
for _ in range(1000):
    average += run_simulation()

print(average // 1000)

Making that script object oriented is compleate overkill but it was fun to write. I've made some assumptions here, mainly that the prisoners are interrogated in a random order and continuously until one of them says "All prisoners have been interrogated".

It usually takes around 10400 interigations before the prisoners are set free. I then started thinking about other issues like what if the interigations are not random. My sister sent me a link to a journal article that looks into all these posibilities. It's a fun little distraction for those who like logic puzzles.

Creative Commons License
Content on this site is licensed under a Creative Commons Attribution 4.0 International License.
Built using Pelican. Based on a theme by Giulio Fidente on github.