After a long hiatus (7 months!) I am finally back to writing. This week I revisited an old problem that Sam Coskey told me a couple of years ago. Some of you will remember this “Secret Santa problem”, which I wrote about before. The problem is:
Sam’s Problem. Is it possible for two people to each choose a natural number so that both numbers are exactly 1 apart and neither person knows who has the larger of the two numbers?
Here are the other posts, which are generally quite short:
The Secret Santa Problem (Part 2)
To summarize the third part, there is an induction argument that shows that this is impossible, but there is a constructive method which seems to solve it. This paradox is fun to think about, and I like to talk to people about it.
While attending a conference in Bonn, Germany over dinner I told Itaï Ben Yaacov about this paradox and he immediately replied:
“Why, this is just the surprise exam paradox. An infinite version, but the surprise exam paradox nonetheless.”
Of course! I have talked to many people about this problem and no one has pointed this out before. Let me remind you of the surprise exam paradox. Actually, I’ll remind you of the unexpected hanging paradox, which is similar:
“A prisoner is told that he will be hanged on some day between Monday and Friday, but that he will not know on which day the hanging will occur before it happens. He cannot be hanged on Friday, because if he were still alive on Thursday, he would know that the hanging will occur on Friday, but he has been told he will not know the day of his hanging in advance. He cannot be hanged Thursday for the same reason, and the same argument shows that he cannot be hanged on any other day. Nevertheless, the executioner unexpectedly arrives on some day other than Friday, surprising the prisoner.” (Quoted from Wolfram/ Mathworld.)
But wait a moment… This seems to really rely on there being a “last day” to start the induction. Well… You have to think about the week “backwards”. (For the set theorists, the week is an infinite set of order type 
Itai turned to me at dinner the next night (on a cold German restaurant patio) and said:
“I am bothered by this story you told yesterday. This ‘surprise exam’ on the infinite week…”
I think that brings the problem to an end though. We have now that Sam’s problem is really the infinite surprise exam problem, which is a hard problem!
Mike Pawliuk - Mathematics 