Secret Santa 3: The Paradox.

Last time I discussed the solution to Sam’s problem:

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?

I established, by induction, that it is impossible to do this. Great. We write “QED” and move on. There is a very convincing counter-argument that was brought to my attention by Jacob Tsimerman and a student at the Winter Canadian IMO camp. They proposed a method that seems like it should solve Sam’s problem in the positive. What exactly is going on in their method? Where is the mistake?

Jacob’s method. Player 1 chooses a large enough number N (say greater than 100); this is now their number. Player 1 writes down the numbers N+1 and N-1 on different pieces of paper and presents them face-down to Player 2. Player 2 chooses one of them and burns the other one without looking at it. The number Player 2 sees is their number.

This method seems to satisfy the conditions of the problem; The numbers are certainly exactly 1 apart and it doesn’t seem like they know who has the larger number. If you were to use this method in real life it isn’t clear if you have the larger number – we don’t know anything about the second player’s action, how can we possibly know who has the larger number?!

Well it comes down to the words “chooses a large enough number N”. Player one cannot pick the number 0, partly because player 1 will know they have the smaller number.

(1) So can Player 1 choose the number 1? If they do, Player 2 will draw either the number 0 (in which case they know that the game has been broken, as they have the smaller number) or they draw the number 2. Since Player 2 has not announced that the game is broken, Player 1 must then know that Player 2 has drawn the number 2. So in either case Player 1 cannot have the number 1.

(2) Can Player 1 choose the number 2? If Player 2 draws the number 1, they know that player 1 wrote down the number 2 (and not the number 0), so they know the game is broken. If Player 2 draws the number 3, then because Player 2 has not announced that the game is broken Player 1 will know that Player 2 has drawn the number 3. That means that Player 1 knows that the game is broken. So Player 1 cannot write down the number 2.

It continues on in this fashion where one of the players always knows that the game is broken. That is a bit of a cop out. Try to work out the case for Player 1 writing down 3. There will be a back-and-forth where Player 2 knows the game is broken because Player 1 said nothing after Player 2 said nothing after drawing his number.  Fun, right?

I was skeptical at first about this because of the amount of calculations this takes. How long do the players need to wait before they know that the game is broken? At first I thought that the number of calculations grew exponentially with the size of number that Player 1 chooses. It turns out that if Player 1 writes down the number 200, then after 200 or so calculations, one of the players will know that the game is broken.

Practically speaking though, humans are incapable of this type of exact, error-free calculations. So practically speaking Jacob’s method does solve Sam’s problem. What about for computer players? Suppose we enforce that after a specified unit of time (say a yoctosecond, seconds) each computer announces whether or not it knows that the game is broken. It seems that if computer 1 chooses a truly enormous number (say greater than a googol bang bang bang) then there just won’t be enough time in the computers’ lifetimes to discover that the game is broken. It is pretty easy to choose an enormous number, so maybe even then Sam’s problem is practically solvable.

What do you think? Is Jacob’s method a legitimate solution to Sam’s problem, or not?