Surprise exam paradox?

Question

I just remembered about a problem/paradox I read years ago in the fun section of the newspaper, which has had me wondering often times. The problem is as follows:

A maths teacher says to the class that during the year he'll give a surprise exam, so the students need be prepared the entire year. One student starts thinking though:

1. The teacher can't wait until the last day of school, because then the exam won't be unexpected. So it can't be the last day.
2. Since we've removed the last day from the list of possible days, the same logic applies to the day before the last day.
3. By applying 1) and 2) we remove all the days from the list of possible days.
4. So, it turns out that the teacher can't give a surprise exam at all.

Following this logic, our student doesn't prepare for this test and is promptly flunked when the teacher does give it somewhere during the middle of the year (but that's my own creative addition to the problem).

This problem reminds me about the prisoner's dilemma for finite number of turns - you have to betray at the last turn because tit-for-tat retaliation is no longer relevant (no next turn), but then that means that you have to betray at the turn before that, and so on, until you reach the conclusion that you can't cooperate at all.

So is the student's reasoning correct or not? Mathematically it looks like it should be, but that would imply that surprise exams are not possible (and they are).

Answer 1

There is a model of knowledge, essentially due to Robert Aumann, in which knowledge is represented by a partition $\Pi$ of a set of states of the world $\Omega$. If the true state of the world is $\omega$, the agent with partition $\Pi$ only knows that some state in the cell $\pi(\omega)$ (the value of the projection at $\omega$) obtained. An event is simply a subset of $\Omega$. We say that an agent knows that the event $E$ obtains at $\omega$ if $\pi(\omega)\subseteq E$. Now let the state space be $\Omega=\{1,2,\ldots,T\}$, where we interpret $t$ as "there is an exam at $t$". Now there is no partition $\Pi$ such that the following holds:

1. The student doesn't know exactly at which date the exam is at any state.
2. If there was no exam at $\{1,\ldots,t-1\}$, then the student knows this at $t$.

Proof: Let $t$ be an element in $\Omega$ such that $\pi(t)$ is not a singleton. Such an element must exist by 1. Let $t'$ be the largest element in $\pi(t)$. By assumption $t'>t$ and so by 2., $\{1,\ldots,t'-1\}$ is a union of cells in $\Pi$ that contains $t$. Since $\Pi$ is a partition, $\pi(t)\subseteq\{1,\ldots,t'-1\}$, contradicting $t'\in\pi(t)$.

---

So at least using the model of knowledge used above, the surprise exam paradox cannot be formulated coherently.

Answer 2

A very nice discussion of the unexpected hanging paradox can be found in chapter 43 of Martin Gardner's The Colossal Book of Mathematics (New York: W. W. Norton & Company, 2001). Numerous references are included.

Gardner, citing O'Beirne, states that "the key to resolving the paradox lies in recognizing that a statement about a future event can be known to be a true prediction by one person but not known to be true by another until after the event."

The teacher giving the surprise exam "knows that his prediction is sound. But the prediction cannot be used to support a chain of arguments that results eventually in discrediting the prediction itself. It is this roundabout self-reference that [...] tosses the monkey wrench into all attempts to prove the prediction unsound."

See also "The surprise examination or unexpected hanging paradox." Timothy Y. Chow. Amer. Math. Monthly 105 (1998) 41-51, a pdf version of which is here.

Answer 3

The fallacy already starts with the first assumption:

1. The teacher can't wait until the last day of school, because then the exam won't be unexpected. So it can't be the last day.

The student cannot know if there will be a test even if the teacher told him so. So it's still a surprise if it happens on the very last day. And since the teacher said it will be a surprise the student wouldn't even consider it to happen on that day.

---

Okay, I try to explain it more formaly. Of course I work with the assumption that the teacher is always telling the truth, the whole truth and nothing but the truth. Otherwise you wouldn't even know if the exam occurs at all. So you wouldn't be able to expect it.

The student uses the three assertions

1. The exam occurs this year.
2. If the exam occurs this year and there is only one possible day left, I can conclude that the exam occurs on that day.
3. I cannot conclude the day ahead of time.

to remove all the days iteratively from the list of possible days.

Assertions 1 and 3 are from the teacher. So we assume that they must be true.

The student disproved assertion 1. So his proof is flawed. One of his assertions must be wrong.

Assertion 1 and 3 are true. So clearly assertion 2 must be wrong.

This means that the student is not able to conclude the day even if there is only one possible day left.

Answer 4

All depends on the definition of "surprise exam."

If the teacher states that an exam will definitely be given such that on any morning of the term through the last day students could never know with certainty an exam was scheduled that day, the teacher has spoken falsely, since, if an exam hadn't been given by the penultimate day students would know with certainty the exam was on the last day.

If, though, the teacher states that an unannounced exam will definitely be given at some point in the term, it seems fair to call that a "surprise exam", since only the final day of the class could be predicted with certainty to have an exam if all the others hadn't. And even then, the certainty of the exam would only be known for 24 hrs (not much time to study an entire term's worth of material). All other days would have significant uncertainty. The teacher's strategy to keep students on their toes would work.

So, the paradox of your question comes when you say, "Mathematically it looks like it should be, but that would imply that surprise exams are not possible (and they are)." Surprise exams of the first type are not possible. Surprise exams of the second type are. When you clarify the definitions, there is no paradox.

Answer 5

There are many ways of formalizing the paradox, in many different fields, and the article (by T. Chow) cited by Joel Reyes Noche, does a good review work.

However, one thing which has always bothered me, is that in most formalizations, the surprise exam can take place in the last day, as legitimately as in any other day. To my mind, this doesn't convey the intuitive meaning of "surprise".

A new approach, given by Ran Raz here, doesn't suffer from this fallacy. He follows the "standard" logic formalization - in which "surprise" means "the exact day cannot be proved in advance (using the statement), from the fact it hasn't occured yet", but adds the clause "or it can be proved that it falls on different days" (since, obviously, if opposing facts can be proved, it is hard to say that the students "know" anything). Now, the interesting thing is, that the exam can't occur on the last day, but the induction argument fails from the unprovability of the consistency of the logical system (a.k.a. "Godel's Second Incompleteness Theorem").

I find this approach interesting and refreshing.

Answer 6

If the student is sufficiently bright to prove that a "surprise" exam is impossible then it would certainly be a surprise to the student, whenever the exam was set.

Answer 7

I agree that all depends on the definition of "surprise exam". If exam isn't a surprise, there is nothing saying that the exam won't be given. So the student should/could conclude (but this isn't necessarily the right thing to do) that the exam won't be a surprise instead.

I was thinking of this problem in terms of probabilities. For example the exam isn't a surprise if the student thinks it will be given at day N and the exam is actually given at day N.

For example the time frame is 1 day only: so the exam will be given today, the student knows about this and there is no surprise, 1 possible options, 0 for surprise P = 0/1 = 0.

The time frame is 2 days only, then:

Day 1: exam at d1 - the student thought d1 => no surprise
       exam at d1 - the student thought d2 => surprise
       no exam at d1 (move to Day 2)
Day 2: exam at d1 => no surprise, everything is in past
       exam at d2 => no surprise

P = 1/4

The time frame is N days, then:

Day 1:   exam at d1 - thought d1 => no surprise
         exam at d1 - thought d2 => surprise
         ...
         exam at d1 - thought dN => surprise
         no exam at d1 (move to Day 2)
Day 2:   exam at d1 => no surprise
         exam at d2 - thought d2 => no surprise
         exam at d2 - thought d3 => surprise
         ...
         exam at d2 - thought dN => surprise
         no exam at d2 (move to Day 3)
Day 3:   exam at d1 => no surprise
         exam at d2 => no surprise
         exam at d3 - thought d3 => no surprise
         ...
         exam at d3 - thought dN => surprise
         no exam at d3 (move to Day 4)
...
Day N-1: exam at d1 => no surprise
         exam at d2 => no surprise
         exam at d3 => no surprise
         ...
         exam at dN-2 => no surprise
         exam at dN-1 - thought dN-1 => no surprise
         exam at dN-1 - thought dN => surprise
         no exam at dN-1 (move to Day N)
Day N:   exam at d1 => no surprise
         exam at d2 => no surprise
         exam at d3 => no surprise
         ...
         exam at dN-1 => no surprise
         exam at dN - thought dN => no surprise

$P = \sum_{i=1}^{N-1} \frac{i}{N^{2}} = \frac{\frac{N\cdot (N-1)}{2}}{N^{2}} = \frac{N-1}{2\cdot N}$