The surprise exam paradox

[tendays]

That thread about the liar's paradox reminded me of that paradox you've probably already heard about (sometimes it's about a guy sentenced to death - I prefer the non-violent instance :o). Can someone help me sort it out?

It goes like this:

The evil professor says to the students: you are going to have an exam next week. I'm not telling you which day, but I am telling you that it will be unexpected (i.e., the day of the exam you won't be sure whether the exam is that day or not).
I'm assuming that the week starts on Monday and ends on Friday.
So this is what the students think:
Okay, it can't be on Friday, because if Friday comes and we haven't had the test yet, then in the morning we'll surely know it's that day. So it will be a day from Monday to Thursday.
After pondering a bit, they realise that it can't be Thursday either, for the same reason: If Thursday comes and they haven't had the exam they'll think "we know it's not Friday, therefore it has to be today". So Thursday wouldn't be a surprise either.
Similarly (by induction), all days are eliminated !
Then they are happy and think the evil professor made a promise he couldn't hold, and don't prepare for the test.
However, the next week, on Wednesday, they have the exam. And all are surprised.
So where is the reasoning incorrect ?

Again, I don't know the answer. I have only ever seen non-convincing arguments.

Edit: Addenda:
1) "an exam": That's one exam, not less, not more.
2) "surprise": On the day of the test, (therefore knowing it was not on any previous day) the students can't prove it is going to be that day.
Note that this is different (stronger) than not being able to say, before, the week starts, what day it is going to be.

[bbctol]

Back up to, say, Tuesday. They know it can't be Wednesday, so are surprised when it is. Any day except Friday is surprising, because they don't expect it on any day.

[3.14159265...]

It has been done. Someone have the link?

[notzeb]

This one's easy! The professor's lying.

...Or he would be lying, if any of the students were smart enough to realize it. Basically, they stupidly believed his lies, and by believing them, they made them true.

Edit: Imagine I told you you'd have a surprise exam tomorrow, and that you wouldn't expect it. It's pretty much the same thing.

[Strilanc]

I think there are a few problems with the story. First of all, "know when the test is" is clearly dependent on time. The problem should probably be rephrased so the students must say "the test is today" at the beginning of the day (and the professor can't just change his mind!). Furthermore, they only get one guess.

If that is the case, then we can't show the test won't be on Friday, because the students could say "the test is today!" on Wednesday, allowing a Friday test. If the students are allowed a guess every day, then they should just say "the test is today!" every time and they will eventually be right.

However, rereading the story it looks like it is stated in such a way to cause the "multiple guesses when you're wrong" scenario. I would bet this is just an example of a contradiction via self reference (the students are considering their own actions based on their considerations of their own actions). In fact, if you do a 'formal' proof of the situation, you get a contradiction (which allows you to then state 'the test is on Wednesday').

[aaronstj]

No, I think the problem is fine as stated. It's not about the students guessing which day the test is and being correct or not, it's about them being able to actually know (logically deduce) which day the test is. The professor asserts that on the day of the test, the students will not be able to logically deduce whether or not the test is that day. That seems a reasonable thing to assert. The students don't believe so, but they're proven wrong. Clearly the students logic is wrong, but I can't quite figure out where exactly.

[tendays]

... First of all, "know when the test is" is clearly dependent on time.

Yes it is. The students' knowledge changes (increases) every day.

The problem should probably be rephrased so the students must say "the test is today" at the beginning of the day (and the professor can't just change his mind!).

Yes, the professor has decided which day the test is going to be before the week starts, and doesn't change his mind. But that is irrelevant anyway - he won't answer any questions about which day the test is on.

However, rereading the story it looks like it is stated in such a way to cause the "multiple guesses when you're wrong" scenario.

Using a more formal notation: T1 is the statement that the test occurs on Monday, T2 for Tuesday, until T5 for Friday.
The week before, the professor says "T1 | T2 | T3 | T4 | T5" (where | stands for "or". Exclusive or, actually.)
Then, on each day (x) before the test, he says "Tx is false".
On the day of the test he says "Tx is true".
The "surprise" component means that on the day (x) of the test, the students can't yet logically infer Tx, and therefore the "Tx is true" statement strictly increases their knowledge.

Now that I wrote this formally I'm starting to have a vague idea of what is wrong, actually.

I would bet this is just an example of a contradiction via self reference (the students are considering their own actions based on their considerations of their own actions). In fact, if you do a 'formal' proof of the situation, you get a contradiction (which allows you to then state 'the test is on Wednesday').

I'm not sure I'm following what you say - they only work by logical inference - they don't make actions or take decisions...

[Belial]

On any given day, they both expect, and don't expect the test. Because they expect the test every day, they don't expect it any day.

The professor collapses probability around their expectation that it *isn't* today, and issues the test.

Quantum students for the win.

[Dashiva]

If it becomes Friday, the students go:

A | B | C | D | E
!A
!B
!C
!D
= E

This is a valid deduction.

On Thursday, it is shorter by one

A | B | C | D | E
!A
!B
!C
= D | E

The question is then if they are allowed to use their future knowledge (acquired on Friday) to conclude !E.

Edit: I'm thinking something like "If they do use Friday to say !E, then they at the same time say D, which invalidates their argument from Friday." but I don't really know how to formalize future knowledge.

[Patashu]

On Thursday, if the exam has not happened yet the students know it must be on friday.
On Wednesday, if the exam has not happened yet the students know it must be on thursday, and not friday. (else they would not be surprised by the certain outcome)
On Tuesday, if the exam has not happened it is actually more likely for it to be on wednesday, now that there's a hint of ambiguity (both wednesday and thursday could reasonably hold it).
And on Monday? Three different days.

Could be any day from tuesday to thursday and work out, assuming my half-assed 5 minute analysis is correct.

EDIT: Oh, could be on monday too.

[jestingrabbit]

http://forums.xkcd.com/viewtopic.php?t= ... light=hang

Its framed differently, but its the same paradox. I don't like any of the resolutions that there are. To avoid the test/hanging, you can just form the expectation everyday that you'll be tested/hanged, and you can logically support your conclusion too. Aparently modal logic can get around this, but I'm unconvinced so far.

[Yakk]

We have an axiom of nonprovability.

Assuming the axiom of probability and the axioms of the test (exactly 1 day next week), we get an inconsistent system.

In an inconsistent system, all statements can be proven both true and false.

As such, you can prove that the exam both happens, and does not happen, each day next week.

I don't see the problem.

...

Now, if you restrict your system from talking about the system, then the axiom of unprobability has to be worded differently. It can say "in a system without this axiom, you could not prove it on any day", which leads to no problems.

[themuffinking]

I'm pretty sure this is an example of 1-step thinking vs. 2-step thinking.

The students think in one step:
1. "We cannot have the test any day of the week."

The professor thinks in two steps:
1. "The students think they cannot have the test any day of the week."
2. "Therefore, I shall have the test Wednesday and take them all by surprise."

If you wanted to expand this, you could add, say, a graduate student.
1. "The professor thinks that I think we cannot have the test any day of the week."
2. "Therefore, he is planning to have the test on a certain day which I cannot foretell."
3. "I shall study."

Basically, it's a chain of "he thinks that I think that he thinks that I think that he thinks..." which can go on forever in certain scenarios. This is one of the reasons why chess is so difficult without the raw muscle of a computer behind it: "he thinks that I think that he thinks that I think that I should move my knight to B5, but I know this, and therefore I should move to B7" while the other player is thinking "he thinks that I think that he thinks that I think that he thinks that he should move his knight to B5, and in assuming this, he knows to move his knight to B7."

This is also used in many scenarios where a door may or may not lead to a trap or a treasure.
A: It's a trap!
B: No, that's what C wants you to think. It's the treasure.
C: A and B will think that I want them to think that it's a trap, and so will believe that this is the treasure, therefore I shall hide my trap here.

In that case, A and C are correct.

[Tchebu]

The flaw in this problem is the fact that it follows circular logic (as in something gets deduced from itself after a number of steps). This is how:

1)IF there is no exam on thursday or earlier (and none after friday for obvious reasons), THEN the exam can't be on friday.

2)IF the exam cannot be on friday THEN it cannot be on thursday (by the same reasoning as number 1, except here, the "obvious reasons" become the fact that we also assume that we proved that it can't be on friday) or on any previous day (by repeating that reasoning again)

so basically every day, we assume the the exam wasnt on any of the previous days, but we only prove that it can't be on any of the previous days BECAUSE we already think we "proved" that it cant be on our day or any of the later days... which means the problem basically says "we cannot have the exam on friday, because we cannot have the exam on friday"

[notzeb]

I still say you should try this much simpler problem before attacking the whole thing.

Professor: "Between tomorrow and tomorrow, you will have a test. You will not expect it."
Student: "Um, WTF? At least one of those statements is false. However, since I'm forced to blindly accept whatever the professor says as fact, I can easily get an A on that test, because everything is vacuously true!"
Student: "Therefore, I don't need to study!"

-next day-

Professor: "Nice try, but I was using quantum logic."
Graduate Student: "I'm surrounded by idiots!"

[Toeofdoom]

This one's easy! The professor's lying.

...Or he would be lying, if any of the students were smart enough to realize it. Basically, they stupidly believed his lies, and by believing them, they made them true.

Edit: Imagine I told you you'd have a surprise exam tomorrow, and that you wouldn't expect it. It's pretty much the same thing.

Basically this sums it up well.

[phlip]

Whether the class can prove the test will take place on day x is, of course, a function of whether or not the test will actually occur on day x (if the test isn't going to happen on Tuesday, the class can't prove it will happen on Tuesday). However, by the "surprise" clause, whether or not the test will happen on day x is a function of whether or not the class can prove the test will take place on day x.

Hence we have a self-reference in the propositions of the question, and, as such, the system is outside the realm of standard true/false logic (like the standard "This statement is false" line). To solve them, you need a variant version of logic... in particular, you have to lose the axiom of excluded middle (ie everything is either true or false) which the class assumes when it says "if it's Thursday, we'll know it has to be today, since it can't be Friday."

[Patashu]

Also, about the whole 'it must be on thursday because it can't be on friday' thing, what if it went something like this?

~Thursday~
Student: The exam must be today! If it was on Friday then when it would have been Friday it wouldn't have been a surprise!
Professor: I knew that you'd think that so I put the exam on Friday. You lose.

[Cataleptic]

The professor makes two statements:

1. There will be an exam in the next N days.
2. At no time will you be able to deduce which day it is on.

It seems to me that the fatal flaw with the student's reasoning is that they can use induction. If you use induction, you have to start with the N=1 case... but the N=1 case is inconsistent, and therefore taints any further deduction.

[Zabi]

On Tuesday, if the exam has not happened it is actually more likely for it to be on wednesday, now that there's a hint of ambiguity (both wednesday and thursday could reasonably hold it).

not true. given that they know that the exam cannot be on Friday without them knowing that it would be on Friday both Friday and Thursday are ruled out because if it's not on Wednesday then on Thursday they know the test will be then or it won't be a surprise, which means that they know it's not on Friday, Thursday, or Wednesday.

If I was the professor, I'd just let them know the exam was canceled, and then have it on Tuesday. That is truly the only way to have the exam be a surprise.

[Aoeniac]

The reasoning is bad because they can only suspect Friday IF THEY HAVEN'T HAD THE TEST YET. So pretend it's Tuesday and so far no exam. The days left to potentially house the exam are Wednesday, Thursday, and Friday.

IF they make it to Thursday AND there's no test, THEN they can suspect a test on Friday as it is the only day left in the week. Seeing as how they then expect the test, doing so will make it so that the professor wouldn't be keeping his word if he gave them a test and they can try to argue their way out of it if he still tries to give it.

The problem is that in order to suspect, and therefor invalidate Friday in the first place, you need to fulfill the two conditions of it currently being Thursday and there not having been a test yet.

Thus, they cannot suspect Thursday either by the same virtue. They need to already be suspecting Friday before Thursday becomes the effective end of the week and therefor also able to be suspected... but the thing is they can't suspect Friday until it's already Thursday!

So... I guess... ultimately the flaw arises in that the professor never said he wouldn't still try to give the exam on Friday to see if anybody would catch him.

[cjr]

There are other ways to make sure the students can't "logically deduce" the day (are you sure that's the same question?)

He can just straight out lie, and do something he didn't say he would do (such as ask everyone to come in on Saturday)

Alternatively, he could roll a fair d5 with the weekdays on it, and set the exam on that day. Again, the students wouldn't know the outcome of the roll, and have no way of recreating the event, so would have nothing to work on. Even with their best rational reasoning, they would only have a 20% chance of getting the day, and so would be just as 'surprised' as not.

One final thought that cropped up while doing this - surely this element of surprise doesn't really work considering the small amount of days? We've already shown that there appears to be more than one answer - a student can prepare themselves for exams on all five days without too strong a mental fatigue. It really doesn't work to say that there is a certain day where every student will be dumbfounded and scramble for their revision notes. It is only if you convince yourself that it will be on Xday that the level of 'surprise' increases.

[tendays]

Thank you all for your replies, I'll study them when I have the time.
I have also started formalising the problem as a bi-modal logic (two modal connectives - one for (discreet) time and the other for students knowledge).
And then suddenly real life caught up and I realised I have an exam in four days and another exam three days after.
(I am just posting this in case someone wonders why I start a thread and then vanish.)

[jordan]

I think the best answer so far is that the professor was lying; or, from another perspective, he was taking a chance that the exam might actually be predictable on the day.

As stated, the problem expresses a contradiction. Let's simplify it a little. We have an ordered set of five statements, from s1...s5. In the context of this example, the statements are equivalent to "the exam is on Monday," "the exam is on Tuesday" etc. As each day passes, the truth value of one of these statements is negated or confirmed, in the prescribed order.

Claim 1. One (and only one) statement is true; i.e. s1 xor s2 xor s3 xor s4 xor s5. We can therefore say with confidence that once four statements have been eliminated, we will know that the fifth statement is true.

Claim 2. You will discover which statement is true when there is still at least one indeterminate statement.

This means that the last statement in order must be false, i.e. s5 is no longer indeterminate. So we can now reduce the set to s1...s4. But now s4 is the last statement in order, and therefore false, allowing us to reduce the set... all the way down to s1, at which point we must conclude by claim 1 that s1 must be true since all the other statements are false. But this contradicts claim 2, since there must be at least one indeterminate statement; so s1 must be false. Contradiction.

So either claim 1 (the exam will definitely be on one of these five days) is false, or claim 2 (you will definitely not know which day the exam is on when that day comes) is false.


A better statement for the professor to make would be that the students will not know when the exam is with the exception of a Friday exam. Here's a rather different take on the problem, from the perspective of the professor. Let's say he writes down the five days on a piece of paper, folds them up and puts them in a hat, and asks his evil colleague to select one at random. He does not tell the students which piece of paper was selected.

From this perspective: on Monday morning, there is a probability of 1/5 that the exam will be today, i.e. an exam today would be quite unexpected. On Tuesday, there is a probability of 1/4, and so on until Thursday morning, when the probability is 1/2. Only on Friday is there a probability of 1 that the exam is today. That is, the students will only know what day the exam is on if the colleague picked Friday.

[Alisto]

Have the exam on Friday. Since logically the exam CAN'T be on Friday, no one will ever suspect it.

Duh.

[Yakk]

The professor says "There will be an exam on friday. You cannot prove there is an exam on friday."

Notice the bare contradiction. The students can prove it will be on friday, and thus prove it won't be on friday.

The professor says "There will be an exam on monday or tuesday next week. You will never be able to prove which day the exam is."

Notice that the contradiction is only thinly vieled. The students can prove that an exam will be on any day. The students can also prove the exam won't be on any day. Just like the 1 day case.

Having 5 days just viels the contradiction a bit more. The same result happens: you can prove and not prove the exam is on each day.

[bbctol]

Well, if the exam is a surprise, that just means it happens on a day when they expect it not to. And they don't expect it on any day. So it's a surprise on any day. Right?
Actually, I still think it can't be friday, and I don't like my own logic. Wah.

[notzeb]

But what if it's a logic professor? (using, quite possibly, nonaristotelian logic?)

[tendays]

Well, if the exam is a surprise, that just means it happens on a day when they expect it not to. And they don't expect it on any day. So it's a surprise on any day. Right?
Actually, I still think it can't be friday, and I don't like my own logic. Wah.

Replace "when they expect it not to" by "when they don't expect it to". E.g. they expect it not to happen on Saturday and don't expect it to happen on Wednesday. K being a knowledge/provability connective and A some logical statement, that's the difference between K(¬A) (which is what you said) and ¬(KA) (which is what I meant).

"Surprise" means that one second before the professor says "you have a test today", the students were unable to prove it with certainty.
That's why if it is on Friday it is not a surprise, because before the professor starts to speak, given that the test had not been given before and can't be given on any later day, the students can easily prove it is that day.
Now maybe Yakk is right and what the professor says is self-contradicting. I will have to think about it when I have more time.

[Patashu]

How is it self-contradictory if the professor showed that he could indeed give an exam without anyone expecting it?

[Patashu]

oops

[dan]

If the students get it wrong, the professor was right, and there is no contradiction. If the students get it right, the professor was wrong - but that means the logic the students used was based on a false premise. The only way the students have a hope of getting the right day is by using a method that does not rely on what the professor said - for example, randomly choosing a day then expecting it on that day.

[notzeb]

BETTER!

We know that some things are true, and some things are provable. Not everything that is true is provable.

Professor:
1. (I claim) that you will have a test by friday.
2. (I claim) that given that the test is not before day x, the statement "the test is today (day x)" is not provable.

Me on friday:
1. the Professor's claim implies that I will have a test today.
2. the Professor may or may not be lying.
3. I cannot prove that I will have the test today (after all, evil professors are prone to lying).

Me on any other day:
1. I may or may not have the test today.
2. I cannot prove that I will have the test today, because I can make a model of a situation which is consistent with everything I can prove, and in which I have the test on friday.

Some other student on friday:
1. I will have a test today. (axiom, from Professor)
2. I just proved that I will have a test today.
3. I cannot prove that I have a test today. (axiom, from Professor)
4. Therefore, I do not exist!

Some other student on any other day:
1. By induction, I cannot have the test tomorrow.
2. I will have the test today. (by axiom from Professor and statement 1)
3. By the same reasoning, I do not exist!

Thus, all students other than me demonstrate acute existence failure. Therefore, all scholarships, student aid, grants, etc. should be paid (in full) to me.

Edit: Argument by Analogy is the only logical fallacy which I support whole-heartedly.

[silverhammermba]

I've always kind of hated this question and mainly because of the ambiguity of "knowing which day the exam is on". That phrase can be written any number of subtly different ways. And I agree with jordan that it's a contradiction.


There's also a critical flaw in the student's reasoning
Think about it:
1. Exam will be given some day Monday-Friday
2. If, come Thursday, the exam has not been given, the students will know it is Friday. So the exam must be given Monday-Thursday
3. Come Wednesday, the student does not yet know if the exam will be given on Thursday or not and thus cannot rule out Friday as well.
4. Thus the exam can be given on any day Monday-Thursday and will be a complete surprise

The key is that information is revealed chronologically.

Basically: you can only rule out Friday once you know that the exam is not given on Thursday.
I present the conjecture: there is no way to determine whether or not the exam will be given on Thursday ahead of time.

I'm very certain in my answer.

[Drostie]

I've always kind of hated this question and mainly because of the ambiguity of "knowing which day the exam is on". That phrase can be written any number of subtly different ways. And I agree with jordan that it's a contradiction.


There's also a critical flaw in the student's reasoning
Think about it:
1. Exam will be given some day Monday-Friday
2. If, come Thursday, the exam has not been given, the students will know it is Friday. So the exam must be given Monday-Thursday
3. Come Wednesday, the student does not yet know if the exam will be given on Thursday or not and thus cannot rule out Friday as well.
4. Thus the exam can be given on any day Monday-Thursday and will be a complete surprise

The key is that information is revealed chronologically.

Basically: you can only rule out Friday once you know that the exam is not given on Thursday.
I present the conjecture: there is no way to determine whether or not the exam will be given on Thursday ahead of time.

I'm very certain in my answer.

Your answer is fundamentally irrational, though I don't blame you for not noticing it.
Let me just generalize the problem a moment, such that Friday is day N and Monday is day 1. You are given the information that the test is on some day in the set {1,2,...,N}, and that it will not be expected on the day it's on.

You admit the premise that, "If, come Thursday, the exam has not been given, the students will know it is Friday."

For this to be a rational deduction, there must be some broader law, like, "if the test is on some day in the set {1,2,...,i} then it is not on day i."

The problem is, if the latter is true, then the students' deduction is warranted, because it sets up a direct inductive claim.

Formally, this is called the fallacy of special pleading, you are saying that the broader logical rule cannot be applied to the set of {1,2,...,N-1}, but applying it willfully to the set of {1,2,...,N}.

Put another way: You seem to be okay with the deduction from the statement that, "Exam will be given some day Monday-Friday" to the statement that, "So the exam must be given Monday-Thursday"

But when I say "The exam will be given some day Monday-Thursday," you strongly deny that this means that "The exam will be given some day Monday-Wednesday", even though that follows the exact same form as the earlier day.

Do you see what I'm getting at? You can't have a cake that you've eaten.

[Vaniver]

Do you see what I'm getting at? You can't have a cake that you've eaten.

You can. It just... doesn't look like a cake anymore.

[Yakk]

OK, let's make this clearer:

There will be an exam on Friday.
You will be surprised by the exam on Friday: there is no way to prove that the exam is on Friday.

This is the exact same problem without the multiple-day recursion. All of the interesting features of the original problem are here.

[gmalivuk]

There will be an exam one day next week. Each day next week, you will not be sure whether the exam will be that day.

(Let's assume the one way to be sure an exam is a certain day is to prove it is that day.)

The problem with the students' reasoning is concluding that the first sentence *must* be false. A correct conclusion would be that, instead, the second sentence is true (the exam date is unprovable) and the first sentence may or may not be true.

On Friday, if the exam has not yet happened, the correct conclusion would be that the exam may be on Friday, or it may not occur at all. In other words, they can't be sure. (The incorrect reasoning comes from assuming the professor's statement is true, and thus concluding that there will be an exam on Friday if not before. But since this reasoning leads to the conclusion that the statement is false, it cannot be correct.)
On Thursday, then, they also can't be sure. Maybe the exam is Thursday, maybe it's Friday, or maybe the professor lied.
Same goes for the rest of the week.

[adlaiff6]

This is a lot like playing hide-and-seek against one person with five hiding spots. They can hide in any of them, and you can check them in one order. There is nothing to stop the adversary from choosing a particular hiding spot, so at the beginning, the probability that he has chosen any specific hiding spot is equal to that of any other spot. Naturally, in the way that knowledge behaves, after checking four hiding spots, you will know where he is no matter what (sort of a sock-drawer or pigeonhole type deal), but there is nothing that the adversary can do about that.

The professor has made a claim which he cannot completely fulfill. There is no way, as knowledge behaves, for him to prevent the students from knowing exactly when the test is by the end of Thursday, so the students should ask for a clarification on the rules.

[silverhammermba]

But, Drostie, we know that the student's argument ends up being wrong in the end. So either logic is inherently paradoxical or the student made a mistake. I am much more in favor of the latter.

I am convinced that time is the key issue here.

The first claim is valid. That is, "The test can't be on Friday because if we haven't gotten the test by Thursday we'll know it's on Friday."

However, there is no way to phrase that without that crucial "if". That is if the test has not been given Monday-Thursday then it can't be on Friday.

You see what I'm saying? Think about it this way:

We know: Exam must be given Monday-Friday
1. Assume the exam is not given Monday-Thursday
2. Then we know the exam is Friday
3. Thus the exam cannot be given on Friday
4. Thus the exam must be given Monday-Thursday
5. Assume the exam is not given Monday-Wednesday
6. (Induction, blah blah blah, etc.)
7. Thus the exam is not given Monday-Thursday

You see? The student's argument proves an assumption that he made in the very first step.