If you’re the sort of person who reads this blog, you’re likely to be familiar with the paradox of the unexpected hanging, which has been floating around since 1943 but achieved popular notoriety around 1969 through the writing of Martin Gardner. But you’re less likely to be aware that the unexpected hanging plays a central role in a wonderful new piece of serious mathematics related to algorithmic complexity, Godel’s theorems, and the gap between truth and provability.
The unexpected hanging might as well be a surprise examination, and that’s the form in which I present this paradox to my students every year: In a class that meets every weekday morning, the professor announces that there will be an exam one day next week, but that students won’t know exactly which day until the exams are handed out.
The students, of course, immediately start trying to guess the day of the exam. One student (call him Bob) observes that the quiz can’t be on Friday — because if it is, the students will know that by Thursday afternoon. After all, if Monday, Tuesday, Wednesday and Thursday mornings have all passed by, only Friday remains. A Friday exam can’t be a surprise exam.
A more thoughtful student (call her Carol) observes that this means the quiz must be on one of Monday, Tuesday, Wednesday or Thursday — and that if it’s on Thursday, they’ll know that by Wednesday night. After all, Friday’s ruled out, so if Monday, Tuesday and Wednesday have passed by, then only Thursday remains. That rules out a surprise exam on Thursday.
Another student (call him Ted) observes that thanks to Bob and Carol, we know the exam must be on one of the first three days of the week — which means that if it’s not on Monday or Tuesday, it must be on Wednesday. Therefore if it’s on Wednesday, they’ll know this by Tuesday night. Scratch Wednesday from the list of possibilities.
Now Ted’s girlfriend Alice points out that the exam can’t be on Tuesday either. Whereupon Bob concludes that the exam must be on Monday. But wait a minute! Carol points out that if they know the exam will be on Monday, it can’t be a surprise. Therefore no surprise exam is possible.
The students, relieved, decide not to study. But they’re awfully surprised when they show up in class the following Tuesday and the professor hands out an exam.
Where did the students go wrong? There is no consensus among the many philosophers and logicians who have considered this problem. The great Willard Van Orman Quine believed that Bob went wrong at the very beginning when he ruled out Friday. (According to Quine, Bob’s argument fails to distinguish between a proof that the exam can’t be on Friday and a proof that the students will know that the exam can’t be on Friday.) Other deep thinkers have accepted Bob’s argument (agreeing that the exam can’t be on Friday) but refused to accept Carol’s (thus refusing to rule out Thursday). You can, if you wish, read a pretty comprehensive survey of this literature here. But even among those who think Bob (or Carol) is mistaken, there is little agreement about exactly why they are mistaken.
Now, I happen to think the surprise examination paradox is pretty interesting as a pure intellectual exercise. But it’s also got important applications. I use it in the classroom to illuminate our discussion of the underlying “backward induction” technique, which economists (and especially game theorists) use all the time in serious arguments. Much more recently, the surprise examination has been used to illuminate some key concepts in mathematical logic, which I alluded to back in the first paragraph of this post. That’s the coolest part of all, and I’ll tell you all about it later in the week.