You are here

One Hundred Prisoners and a Light Bulb

Hans van Ditmarsch and Barteld Kooi
Publication Date: 
Number of Pages: 
[Reviewed by
Ittay Weiss
, on

I like mathematical riddles. I particularly like mathematical riddles that harbour deep insights, or at least that contain more than just what appears on the surface of the riddle. The book appears to have been written for a readership not accustomed at all to mathematical reasoning, so much so that the average student who already completed just a few courses at the undergraduate level may find the book too slow and overridden with details. My review is primarily aimed for the reader feeling comfortable enough with mathematics (though not necessarily an expert), though I address the book in a slightly broader context.

The book presents 11 mathematical riddles and a chapter forming an introduction to epistemic logic. Each riddle is treated by first presenting the riddle, and then promptly proceeding through some discussion, or a story, presenting an analysis of the situation and at times some failed attempts, and then the solution. Then some variations are offered and a short historical review is given. The presentation does not particularly encourage the reader to first attempt to arrive at a solution. The problems are not particularly difficult, so perhaps an initial paragraph suggesting a few lines of attack, or some hints, would have served the reader better.

The problems discussed are classical and well-known; some of them form part of what should be the standard treasury of riddles any educated mathematician should be aware of. The first problem is the one where two consecutive natural numbers are chosen (at random, glossing over the impossibility of doing so uniformly, a fact not crucial for the problem, but one that should be mentioned). One number is shown to Anne and the other to Bob. When either Anne or Bob knows the other players number, (s)he announces so. Otherwise, in turn, they proclaim “I do not know your number” (the situation described in the book is a concrete instance of this protocol). This is really a beautiful problem that is well within the reach of most readers. In fact, I would describe it as an easy problem. A student should be able to prove (by induction) that if the chosen numbers are \(n\) and \(n+1\), then the game will end after \(n\) turns, with the person holding the number \(n\) correctly announcing the other players number. The true interest in this riddle, the deeper mathematical content it harbours, is what information is exchanged, particularly with the first few announcements of “I do not know your number”, between the players. I find it unfortunate that the book does not address that at all.

The second problem is the famous unexpected hanging, or surprise examination paradox. I still vividly remember having spent many nights in bed when I was a boy thinking about this wonderful problem. The book offers a resolution of the paradox by an argument which I find completely unsatisfactory. It is mentioned that there are more than 100 articles devoted to this problem, indicating its complexity, and I find the treatment of it in this book to be particularly simplistic.

The third problem is the famous muddy children, or dirty logicians, or unfaithful wives problem. This problem shares the same underlying deeper mathematical content with problem one. That, however, is not highlighted; in fact, the whole concept of complete knowledge is not made clear enough.

The fourth problem is the Monty Hall problem, which I find to be adequately treated. The next problem is the Russian Cards problem. There, after the problem is presented, follows a long discussion of an attempt solution which I find rather tedious and ad-hoc. There is no logical bridge built between it and the so called “correct” solution (modular arithmetic!) which is just presented without any hint on how to arrive at it. It is unclear what the purpose of the long discussion is and it would have been better to instruct the reader on how to arrive systematically at the elegant solution. Problems six and seven are very similar to each other and do not hold great secrets. They are of the form: two numbers are chosen, their sum is so and so, their product is so and so, followed by some peculiar looking dialogue leading, somehow, to knowing what the numbers are. These are nice riddles.

Problem eight is the two envelope paradox. This is a truly splendid problem with very challenging variants. I find the treatment of it rather lacking. Again, the inability of choosing the values uniformly is not discussed (and here it is more pertinent) and the really challenging variants are not described.

The next problem is the one described in the title of the book, a classical riddle which perhaps is difficult to solve if one expects the protocol to be extremely complicated. Once one convinces one’s brain to first try some simple ideas, the solution is likely to pop up sooner or later. Again, one does not gain much mathematical insight from this problem.

Problem ten is the famous gossip protocol, well-known to computer scientists, and well-presented in the book. Finally, problem 11 is a rather strange discussion of the game Cluedo. I fail to see how it fits in with the rest of the book as it does not really contain much more than some (rather obvious) strategies for playing the game.

To conclude, I find the book aims too low (even with a completely mathematically novice reader in mind) and misses several important marks. For mathematics students there are better books with wonderful riddles to pass one’s time with.

Ittay Weiss is Lecturer on Mathematics at the School of Computing, Information and Mathematical Sciences of the University of the South Pacific in Suva, Fiji.