University of Otago logo. Computer and Information Science Seminars

Seminar Homepage


Hans van Ditmarsch, Department of Computer Science


Logic Puzzles


St David Seminar Room 3 - 1:00 pm, Friday 14 November
Note: Different location from usual


Since the 1940s various so-called epistemic puzzles have become known, wherein typically announcements of ignorance surprisingly lead to knowledge, or employing other puzzling ways to make individual knowledge into common knowledge. A well-known example is the Muddy Children Problem. Far too well-known, so this talk will NOT be about the Muddy Children Problem. Instead, we will present and analyze some other, possibly less well- known puzzles. Two examples are given below.

What is my number?

Each of agents Anne, Bill, and Cath has a positive integer on its forehead. They can only see the foreheads of others. One of the numbers is the sum of the other two. All the previous is common knowledge. The agents now successively make the truthful announcements:

What are the other numbers?

One hundred prisoners and a lightbulb

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 (assuming that at any stage every prisoner will be interrogated again sometime)?

Last modified: Tuesday, 11-Nov-2008 13:55:28 NZDT

This page is maintained by the seminar list administrator.