Posterous theme by Cory Watilo

Filed under: xkcd

Math Puzzle « xkcd

Math Puzzle

This cool puzzle (and solution) comes from my friend Mike.

Alice secretly picks two different real numbers by an unknown process and puts them in two (abstract) envelopes.  Bob chooses one of the two envelopes randomly (with a fair coin toss), and shows you the number in that envelope.  You must now guess whether the number in the other, closed envelope is larger or smaller than the one you’ve seen.

Is there a strategy which gives you a better than 50% chance of guessing correctly, no matter what procedure Alice used to pick her numbers?

I initially thought there wasn’t, or that the problem was paradoxically defined, but it turns out that it’s perfectly valid and the answer is “Yes.”  See my first comment for an example of one such winning strategy.

This puzzle is similar to, but not the same as, the two envelopes paradox.  For more time-devouring reading, see Wikipedia’s List of Paradoxes.

22 Responses to “Math Puzzle”

  1. xkcd says:

    Strategy:

    Call the number you saw "x". Use the logistic function to calculate p(x)=1/(1+e^-x). Choose a random real number between 0 and 1. If it's lower than p(x), guess "lower". Otherwise, guess "higher".

    In other words, guess "lower" with probability p(x), and "higher" with probability 1-p(x).

    This works because p(x) is a function which is 0 at negative infinity, 1 at positive infinity, and increases monotonically in between. So for any pair of numbers, if you call the smaller one A and the larger one B, you have a (slightly) better chance of guessing “lower” if you saw B than if you saw A. Your overall chances of guessing correctly — given that there is a 50% chance you’re seeing A and a 50% chance you’re seeing B — are:

    N = 0.5 * (1-p(A)) + 0.5 * p(B)

    (remembering that p(x) is 1/(1+e^-x))

    Since p(A) is always smaller than p(B), N is always greater than 50%. If Alice picked 1.0 and pi, your chances of guessing correctly are 61.37%. If Alice picked 10 and 11, your chances of guessing correctly are 50.00053%. No matter what two numbers Alice picked, the chance of guessing right is always better than 50%. Sometimes it’s only better by a tiny, tiny amount, but it’s always better.

    An important thing to keep in mind here is that there’s no such thing as a random sample of all the numbers. There’s no way to choose one integer at random, where every integer has an equal chance of being chosen. (For more on this, see this article.) Similarly, there’s no such thing as a randomly-chosen function out of all the possible functions. You can’t try to model Alice’s process by figuring out the chances her procedure (or numbers) will fall into one category or another because you do not know what procedure she’s using.

    For another version of this puzzle, see question B here and the solution here. If any of this seems wrong to you, try writing a program to simulate the game as you understand it and measure the probabilities yourself. You’ll find that there’s no method Alice can use to pick the numbers that keeps you from having at least a slightly better than even chance of winning (although if she picks two particularly large positive or negative numbers, the difference is probably too small to measure).