One Hundred Prisoners and a Light Bulb — van Ditmarsch & Kooi

You and two other logicians (Alice and Bob) are in a room. A controller comes in and paints a spot onto each of your foreheads. You can each see the others’ spots (Alice and Bob both have black spots) but not your own. The controller tells you all that all the spots are black or white, and at least one of you has a black spot. Then the controller asks if anyone knows the colour of their spot. Everyone says no. The controller asks the same question a second time: again, everyone says no. The controller then asks the same question a third time. What do you say now?

This is one of the most well-known puzzles based on Dynamic Epistemic Logic, which deals with reasoning about knowledge in this kind of situation. This book has a bunch of such puzzles, and discusses the solutions and related matters in illuminating detail.

To solve the puzzle, suppose your spot is white. Since Alice said she didn’t know the colour of her spot (the first time), she must be able to see at least one black spot (since if she saw two white spots, she would know that hers is black). Therefore (since we’re assuming that your spot is white), Bob must have a black spot. Bob knows all this, so when the controller asks for the second time, Bob would say that his spot is black. But he doesn’t, so your original assumption must be wrong. Therefore you must have a black spot, and you say so, to an approving nod from the controller.

Of course Alice and Bob will follow similar reasoning, so when the controller asks for the third time, all three of you will say that your spots are black.

The funny thing is that this is only possible because the controller told you that at least one of you has a black spot. It seems that this gives you no information, since you all already know that (since you can actually all see two black spots). But actually it does give you new information. For example, you already know that there is at least one black spot, and you know that Alice knows it. But you don’t know that Alice knows that Bob knows it, until the controller makes the announcement.

If you understood all that then you will love this book. It has treatments of this and many other classic puzzles such as the Two Envelopes paradox, the Unexpected Hanging, and the Monty Hall problem. There is also a discussion of the dynamics of gossip, and a great analysis of the game of Cluedo.

And then there is the title puzzle, where you have to figure out how a hundred prisoners can communicate with each other by means of a single light bulb. Like all the other chapters, this starts out by stating the puzzle, then analyses it and works out the solution. Along the way, related puzzles and questions are asked and discussed, with answers in the back of the book.

This book isn’t the final word on these puzzles: the approach works well for situations requiring long chains of math-like reasoning, but not so well for conceptually tricky puzzles like Two Envelopes and Unexpected Hanging. Still there are new insights to be had here, even if (like me) you have thought about some of these puzzles for years. (Hey, everybody needs a hobby!)

The authors give many academic references in the book. It was nice to see citations of work by the Swedish logician Krister Segerberg, whom I studied under at university many years ago. I still fondly recall his fascinating and engaging lectures on modal logic. (Yes, really. And then I’d spend my spare time thinking about the Unexpected Hanging paradox. I could have been a logician.)

The tone of the book is casual and it’s pretty readable, considering the complexity and subtlety of some of the concepts. Each chapter also has a quirky illustration which continues the charmingly idiosyncratic feel. Still, the final chapter, an overview of dynamic epistemic logic, would be pretty tough going if you haven’t encountered modal logic before. (And it’s no walk in the park even if you have.) But you can always skim over the rocky patches and still get a lot out of this book. It might even be useful if you ever get sent to prison.

This review is about , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *