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, $10^{-24}$ 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?

 

This entry was posted in Full Article, Problem Solving and tagged , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

3 Comments

  1. Chris
    Posted May 17, 2012 at 2:09 am | Permalink

    I’m unconvinced by your induction here, as I don’t see how the k+1 step generalizes to larger numbers. If you write down 1220 and I pick either 1219 or 1221, how does one of us deduce that the game has been broken?

    • Micheal Pawliuk
      Posted May 17, 2012 at 9:21 am | Permalink

      So you certainly have one half of the paradox down. Yeah, so how can I conclude that 1220 is either the higher or the lower number?

      Also, remember that in this game we are perfect logicians. (Which isn’t a good assumption in real life.)

      IF we both know that 1,2 and 3 can’t be chosen, then the writer can’t write down ’4′ (because either the picker will get ’3′ and know that he has the smallest number, or he will get ’5′, say nothing, then the writer will know he has the smaller number). I guess your issue here is that ahead of time both players need to agree that 1,2,3 are not writable. Then they would have to agree that 4 is not writable, and same with 5 or 6 or whatever.

      What might be not satisfying here is that the induction kind of hides the actual algorithm for the players to decide who has the smaller number in Jacob’s game. The induction argument seems to produce a type of “there exists an algorithm” without actually producing this algorithm.

      The algorithm in this case is pretty horrendous, but is something computers could do. Maybe the game goes like this:
      Player 1 writes. (Note he cannot write 1.)
      Player 2 picks. (If he has ’1′ he announces “the game is broken”. Else, he says “all good for now”.)
      Neither player has ’1′
      Player 1 – If he has ’2′ he announces “the game is broken”. Else, he says “all good for now”.
      Player 2 – If he has ’2′ he announces “the game is broken”. Else, he says “all good for now”.
      Neither player has 1 or 2
      Player 1 – If he has ’3′ he announces “the game is broken”. Else, he says “all good for now”.
      Player 2 – If he has ’3′ he announces “the game is broken”. Else, he says “all good for now”.
      Neither player has 1,2 or 3
      etc.

      This back and forth will end after O(the writer’s number) many steps.

      I think this should make it clearer.

      • Micheal Pawliuk
        Posted May 17, 2012 at 9:24 am | Permalink

        I forgot that I allowed 0 to be chosen. My argument needs to be adjusted in the obvious way.

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>