This is another old paradox, which I'm posting mostly because I like the author's style in presenting it:
In the Hanged-Man Paradox, a man, K, is sentenced on Sunday to be hanged, but the judge, who is evidently French or enamored of the French wit for surprising those sentenced to the guillotine in their last moments, orders that the hanging take place on one of the next five days at noon. Smiling wistfully, he says to K, "You will not know which day until they come to take you to the gallows."
K, who has evidently been condemned for logical perversions, cannot prevent his mind from nevertheless trying to figure out in advance which day will be his last. He quickly realizes it cannot be Friday, because if he has not been hanged by Thursday noon, he will know nearly a full day before they come to get him that he will be hanged on Friday. He is simultaneously pleased at his cleverness and depressed that he has pushed his date with the gallows closer to Sunday.
Soon enough, he realizes that if Friday is logically excluded, then so is Thursday, because if he has not been hanged by noon Wednesday, he will know that, Friday being excluded, his date must be Thursday. In like manner, he can exclude Wednesday, Tuesday, and Monday. As a logician, he smugly concludes that the judge's decree is false. On Thursday noon he is hanged. The paradox is that he is surprised when they come to take him to the gallows.
(One can easily think up less macabre relatives of the Hanged-Man Paradox, such as the Surprise Quiz, a device with which we are all familiar and by which no doubt many of us have illogically been surprised.)
Russell Hardin, Collective Action 147 (1982) (paragraph breaks added). (Of course this isn't a real paradox — just a cautionary tale.) Hardin concludes (p. 148): "His problem was that facing a hangman focused his mind a little too admirably."
P.S. On people named K, see Kozinski & Volokh, The Appeal, 103 Mich. L. Rev. 1391 (2005).
UPDATE: AnonVCfan refers, in the comments, to the "less refined, ugly cousin of this paradox," the famous dialogue from The Princess Bride. I'll reproduce here what I wrote in the comments: "I see the Princess Bride dialogue as illustrating the fact from Game Theory that the game of Matching Pennies has no Nash equilibrium in pure strategies. The Hanged Man's paradox is 'simpler' in a way, because all you need to refute it is elementary logic."
UPDATE 2: Just so no one gets confused here — this paradox is only "simpler" in a way. It's got an intuitive explanation, but in fact it's very hard, and logicians have written like a hundred articles about it. For a good overview, see this paper by Tim Chow. I can follow the gist of it, but the technical aspects are beyond my knowledge of logic.