Friday, January 13, 2006

Riddle...

I found the following post in the annals of a usenet group comp.dsp ( well my friend is a member of that group and he asked me this riddle). Here it goes:


This little gem was in one of Raymond Smullyan's books:

A philosphy student walks into class one day and his
professor makes the following announcement: "We will
have a pop quiz sometime next week. When you first come
to class on the day of the quiz, you will not know whether
or not the quiz is going to be given on that day."

Being logical, the student began reasoning to himself:

"If the professor waited until Friday to give the quiz,
then I would know that the quiz would have to be that
day. So it can't be Friday. If the professor waited until
Thursday to give the quiz, then, since I know it can't
be Friday, I would know it had to be that day (Thursday).
So it can't be Thursday."

He proceeded along this line of reasoning all the way back
to Monday, concluding that the quiz could not be given on
any day next week. What is the flaw in his logic?




I have racked my brains on this one... let me know if you find an answer.
Gives a vague usage of Godel's theorem.... you might want to check that out.

4 comments:

  1. It's an incorrect use of induction. You tend to think he's doing that, but the thinking is all wrong.
    Using induction, you would first prove that it's true for Friday. Then you would have to prove that if day X can't be a quiz day => day X - 1 can't either. That statement is obviously false.
    The key is to realize that X => X - 1 lacks context (specific days), while the reasoning used by the student is context-biased (Friday -> Thursday, etc). He's building a stairway to heaven with 2 steps. Damn, that was deep.
    Cool riddle. Tried to resist but I couldn't. I love those.

    ReplyDelete
  2. I don't agree with the first comment. The prof's statement is inherently paradoxical, a bit like saying "This statement is false" . If that statement were true, then it would be false at the same time... or vice versa. Much the same way, with his paradoxical announcement, the prof ensures that the students really have no idea when the test is going to be, somehow making a paradox come true... whew!

    Vinayak

    ReplyDelete
  3. He has not used induction in the way you are comprehending it. He proves it for friday, then he does for thursday and so on (well it is induction) but he is not assuming that it is true for day X.... he proves it, so it is different from the normal induction based on assumption... and context-bias also makes no sense as he assumes fri>thur>wed>...>monday . I dont see whats wrong with that.

    And if I am wrong and you did solve the question, then I guess u solved an unsolvable question, and proved Godel's theory of incompleteness false. I guess the statement is a paradox of some kind. Infact the whole book from which it is extracted, contains unsolvable riddles

    ReplyDelete
  4. Commenting on my comment above, the moral is that the professor's statement manages to be a paradox and a non-paradox at the same time, which gives us another paradox. Extending the logic, we have an infinite recursion of paradoxes! The end of the world is near!!

    Vinayak

    ReplyDelete