I love a good paradox – especially ones I can’t see a resolution to. I’ve run into this one a few times and wanted to look into it further.
The story is as follows. A teacher is worried that her class isn’t working consistently through the term, choosing instead to “cram” on the night before an exam. So she announces to the class that there will be a quiz on the work they will cover this week. It will be a surprise quiz, sometime next week. The students, not knowing which day the quiz is on, will not have the option of staying up the night before. They must work consistently so that they are always prepared for the quiz.
One enterprising student, however, quickly realises that the test cannot be on Friday. His reasoning is sound – suppose that a student hadn’t worked consistently through the week. Suppose it is Thursday night, and the quiz hasn’t happened yet. Then the student knows that they should stay up all night and cram, which defeats the purpose of the surprise quiz. Thus, the quiz won’t happen on Friday.
So far, so good. But suppose that it is Wednesday night, and the quiz hasn’t happened yet. The quiz must be on Thursday or Friday. But we just saw that it won’t be on Friday. Thus it must be on Thursday. So the student should stay up all night cramming. Which defeats the purpose of the surprise quiz. Thus, the quiz won’t happen on Thursday.
You can see guess what happens next. On Tuesday night, the student would know that the quiz was on Wednesday. On Monday night, the student would know the quiz was on Tuesday. Thus, the student knows that the exam is on Monday, so it is obviously not a surprise quiz. The student concludes that there is no such thing as a surprise quiz.
On Tuesday, the teacher hands out the surprise quiz. The student is, frankly, surprised.
Any mathematicians out there will recognise an induction. Mathematical induction is a form of proof that works like this:
We are attempting to prove a set of statements U(n), where n = 1,2,3 … For example, U(n) could be the mathematical formula:
U(n): 1 + 2 + 3 + … + n = (n2 + n)/2
Since we have an infinite number of statements, we can’t check them one-by-one. Instead, we line them up like dominoes, and then push the first one over. More precisely, we prove the following
Step 1: If U(n) is true for any particular value of n (say, n = k), then it is true for the next value of n (i.e. n = k + 1).
Step 2: U(n) is true for n = 1 i.e. U(1) is true.
Step 2 says U(1) is true. Thus, by Step 1, U(2) must be true, because U(1) “knocks it over”. But then, by Step 1, U(3) must be true, because U(2) knocks it over. And so on.
Returning to the surprise quiz paradox, a number of the discussions of the paradox on the net (e.g. here and here ) suggest that any attempt to put the paradox in the form of an induction will fail because the term “surprise” cannot be given a precise, mathematical meaning.
However, such a formulation has been given here, in one of the comments. The problem is set out as follows:
Premise 1: On exactly one day out of the next n days, there will be a quiz.
Premise 2 (the “surprise” requirement): On the evening of day k (given that the quiz didn’t happen on days 1,2,…, k), there does not exist a proof that the quiz will be on day k+1.
The claim, then, is that these premises are inconsistent. This is shown as follows.
If the quiz was to occur on day n, then on the evening of day n – 1, there would be a simple proof that the quiz would occur on day n:
Proof:
- The quiz must occur on one of the days 1,2,3 … n (premise 1)
- The quiz did not occur on days 1,2,3 … n-1 (by assumption)
- Thus, the quiz must occur on day n.
Since premise 2 forbids such a proof, the quiz cannot occur on day n.
Now the induction shows itself. If premise 1 holds, but premise 2 requires that the quiz cannot happen on day n, then we can formulate a new premise:
Premise 1a: On exactly one day out of the next n – 1 days, there will be a quiz.
But Premise 1a, along with premise 2, can be used to formulate this premise:
Premise 1b: On exactly one day out of the next n – 2 days, there will be a quiz.
And so on. Thus, we reach the conclusion that the announcement of a surprise quiz to the class is self-defeating.
(At this point I am reminded of a passage in John Barrow’s book, “Impossibility”, where he presents a similar argument along the lines that you can only predict the future if you keep the prediction to yourself. That is a topic for another post.)
At this point, I will not attempt to resolve the paradox, because I’m not sure what the resolution is. I’m told that many philosophers have written papers on this very paradox in its various forms (other versions include a man sentenced to hang). I’ll simply leave you with a list of references to further investigation, and invite you to provide your solutions.
Wikipedia: Unexpected hanging paradox
Stanford Encyclopedia of Philosophy: Epistemic Paradoxes
PrawfsBlawg – especially the discussion in the comments.
Cornell course notes: Discrete Mathematics in Computer Science – Induction
“What is a proof?” – Robin Cockett, University of Calgary
Letters to Nature 