100 prisoners and a light bulb
There are days when I feel particularly proud of myself, and today is one of those days.
It’s Friday the 20th of August, that is the last day of ESSLLI 2010. The morning lecture was the last lecture of Hans van Ditmarsch’s DEL course, and at the end of it he presented a “100 prisoners and a light bulb” puzzle, asking us for the solution.
Unexpectedly, I’ve found the solution, but didn’t dare saying it aloud, since I was convinced it was wrong. Once prof. van Ditmarsch told everyone what it was, I was still convinced it can’t be true, and even Karolina (who understood everything very well) wasn’t able to convince me that it actually works. That’s a perfect example how positive introspection doesn’t apply to some agents (i.e. me).
Here’s the puzzle (taken directly from Hans van Ditmarsch’s slides), go on and try to figure out a solution:
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 may 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?