One Hundred Prisoners and a Light Bulb

Hans van Ditmarsch, Open University, the Netherlands

ABSTRACT

The following riddle that came to me by way of the well-known computer scientist Moshe Vardi, was spreading like
wildfire while I was teaching at the logic summer school ESSLLI 2003 in Vienna:

” 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 will, obviously, present a solution. But this talk will mainly address such puzzles of knowledge in general. There are many others,
such as the ‘Muddy Children Puzzle’ (also known as the ‘Wisemen Puzzle’), ‘Surprise Examination’, ‘Monty Hall’,
etc. They often involve a (seemingly) paradoxical aspect making agents knowledgeable by announcements of their ignorance.

More information on such puzzles is found on http://personal.us.es/hvd/lightbulb.html .

This also refers to the book entitled ‘One Hundred Prisoners and a Light Bulb’, co-authored by me and
Barteld Kooi (Groningen), and that is currently available in Dutch, English, Chinese, Japanese.

There is a strong relation between such puzzles and the area in logic known as ‘dynamic epistemic logic’.