Dr. Dobb's Journal June, 2005
By Michael Swaine"The prospect of hanging concentrates the mind wonderfully."
—Samuel Johnson
In his columns in Scientific American and in a book titled The Unexpected Hanging and Other Mathematical Diversions, Martin Gardner explores an intriguing paradox. It first saw print in 1948 and has been cast in many forms, involving surprise inspections, class-A blackouts, pop quizzes, hidden eggs, and card tricks. Patrick Hughes and George Brecht devote 20 pages of their book, Vicious Circles and Infinities to the paradox.
Although the paradox has been richly analyzed, there is one approach that I've never seen. Perhaps I missed it, or perhaps the approach I have in mind is just wrong. But for what it's worth, I thought I'd present my algorithmic analysis of the "Paradox of the Unexpected Hanging."
The paradox: On a certain Saturday, a man is sentenced to be hanged. The judge, known to always keep his word, tells him that the hanging will take place at noon on one of the next seven days. The judge adds that the prisoner will not know which is the fateful day until he is so informed on the morning of the day he is to be hanged.
The prisoner is elated, convinced that he will not be hanged. He reasons as follows: If he is alive on Friday afternoon, he will know that he is to be hanged on Saturday. But this contradicts the judge's assertion that he will not know his hanging day in advance. So his execution cannot be scheduled for Saturday. Therefore, Friday is the last day on which he can be hanged in keeping with what the (truthful) judge has said. But this means that if he is alive on Thursday afternoon, he knows at that point that he will be hanged on Friday—because Saturday has been conclusively eliminated. And by recursion, the prisoner reasons that he cannot be hanged on any day of the week. He is serene.
Thursday comes around and he is informed that he is to be hanged that day—a completely unexpected hanging. The judge spoke the truth. Where did the prisoner's reasoning go wrong?
It is entertaining to see the subtle ways in which some have gone wrong in trying to unravel the paradox. It is not, as some think, trivial. The judge's statements do not appear to be contradictory, the prisoner's reasoning seems to be perfectly logical, and yet something must be wrong with one or the other. We are tempted to suspect the judge of predicting something impossible, but then it turns out to be true. What's the resolution?
I think that the difficulty arises from confusing a prediction with a principle. The judge is not merely predicting that the prisoner will be surprised, he is saying that it is impossible for the prisoner to know the date of his execution in advance. This is a stronger claim and cannot be demonstrated by a single example.
In effect, the judge is claiming that there exists an algorithm for execution-day selection, and asserting that the prisoner cannot in principle determine the outcome of the algorithm early.
So can there be such an algorithm? I say no. Clearly the algorithm can't be something like "Choose Thursday." If that were the algorithm, the prisoner would know that Thursday was the day. So the algorithm must be probabilistic, such as "Choose Monday with probability 1/4, Tuesday with probability 1/4, or Wednesday with probability 1/2."
If you're thinking that there could be several algorithms like "Choose Thursday" and "Choose Wednesday," and that the judge could choose one, you're just multiplying algorithms, because then you have to specify his algorithm for choosing among these algorithms, and you're back with a probabilistic algorithm. Thus there is only one algorithm, thus the prisoner can, in principle, deduce what it is. It is against this fully informed, perfectly reasoning prisoner that the judge makes his strong claim.
But any such probabilistic algorithm has a last day to which a nonzero probability is assigned, and if the judge or his random number generator picks that day, the prisoner will know his fate on the preceding afternoon.
So there is no algorithm with the described properties, and when the prisoner is surprised it only shows that he guessed wrong.