Induction – Understanding the Surprise Exam Paradox

inductionparadoxes

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).

Best Answer

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.

Related Question