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.

409 thoughts on “Math Puzzle

  1. Peter Hosey: You note on Flickr: I do know what an asymptote is; I’d sampled the function at x=10 and Grapher said “1.0000”.

    With my handy calculator program, I note that it’s actually 0.999954602 — that is, Grapher didn’t display enough significant places.

  2. The solution seems like it offers a reasonable (in math terms) explanation, but there’s a few flaws in my view:

    Two numbers are picked by an “unknown” process, where the proof relies on pseudo limiting the set or selection process by saying you can’t randomly choose from anywhere at an equal probability, implying a smaller unknown set. While limiting the set arbitrarily may be one issue, the main issue is this still has no correlation to the relationship between the chosen numbers.

    You can guess that if I pick 2 numbers between 1 and 10, and the first you see is 2, that the second will likely be higher then 2. If I pick two points on a circle, is the second closer to the left or right side of the first? There’s no way to tell if you just see a circle with a point on it.

    The proof seems to be trying to lower the probability of the second number being on one side of the first (between the first number and 0) by trying to find the smaller set of numbers, when the size of the set of numbers on either side of the first should be infinite according to the problem.

    The random envelope is a complete red herring in terms of the problem if the two numbers are indeed secretly chosen, so can be ignored.

    Verifying the generated probabilities in the supplied proofs are impossible (setting aside that the proof adds limitations the original problem didn’t have) due to even the generated probabilities being so close to 50% that any sample data would have such a large margin of error as to be useless.

  3. Does it still work if the number you see is 0? I feel like that would break down exactly 50-50. Or maybe I’m looking at it incorrectly?

  4. The solution in the first post works. If you didn’t understand the explanation there, or still feel slightly confused, perhaps my attempt at an explanation will help somewhat.

    First note that the question and solution still work if you replace the real numbers with an ordered set with at least two elements, e.g. the numbers 1 to 10. This may make it easier to think about.

    Imagine instead of numbers in the envelopes, you had cards with the labels “Big” and “Small”. The recipient adopts the following strategy:
    * If he opens “Small” first, he says “less” with probability p, and “greater” with probability 1 – p.
    * If he opens “Big” first, he says “greater” with probablity 1 – p, and “less” with probability p.

    Remember that both possibilities are equally likely. Therefore, this strategy has a probability of success of 1/2.

    Now what if we could find some way of increasing this probability? It would be nice if we could instead have a strategy:
    * If he opens “Small” first, he says “less” with probability p, and “greater” with probability 1 – p.
    * If he opens “Big” first, he says “greater” with probability 1 – q, and “less” with probability q (for some q > p).

    The probability of success in the second case has increased, so by comparison with the first strategy this has a probability of success that is greater than 1/2.

    With numbers on the cards, this is possible. Assign a probability of saying “less” to each number, so that higher numbers have higher probabilities. This has the result that whatever pair of numbers occur in the envelope, the probability of saying “less” will be less for the lower number, and the probability of success is greater than 1/2.

  5. 0 is a positive number. Now seeing as infinity isnt exacty a real number then you will have a bias no matter how small in one particular direction that you can apply to any formula.

    If you go into negative numbers the same still applies as you still have a bias due to the 0 being the median in the series.

    This is just me taking a quick shot at this.

    Also ReCaptcha recognition authorising is bullshit.

  6. I’ve thought about the problem some more, and there is something that is troubling me about it.

    We say that there is a greater than 50% chance of choosing correctly. But crucially, we don’t have an *actual value* for the probability. If we are to accept the possibility of an unknown probability, then what stops us arguing that the probability of success is either 0% or 100%, we just don’t know which one it is until we open the other envelope?

    To work round this difficulty, we could rephrase the problem slightly. Two envelopes will be given as before. Then we have to come up with a strategy that will, in the long run, successfully say whether the other envelope is larger more than half the time. (We’ve taken a “long-run” definition of probability and replaced an equality with an inequality.)

    This works but a short thought makes one realize that it is nonsense – once you’ve done it once, you *know* what’s in the envelopes – so it’s silly to carry on applying the probabilistic strategy when you know the answer!

    The only way out is to assume that a new pair of envelopes is given every time. But this gives us another problem. If the numbers in the envelopes are chosen in the right way (by repeatedly increasing them and staying above a certain number for long enough), the long-term proportion of correct guesses could easily converge to exactly half.

    I believe the solution to this is to restate the problem once again – find a method that will ensure that the probability that the proportion of successes so far will eventually go and stay strictly above 50% is 1.

    I hope some of this makes sense.

  7. waldo: Without going too far in to definitions, a real number is any number between negative infinity and positive infinity. It needn’t be a whole number, it needn’t be expressable as a fraction (it doesn’t even need to be the solution to a non-constant polynomial of rational coefficients). It does, however, need to be non-complex which, in short, means no square roots of negative numbers.

  8. @xkcd

    Interesting problem, thanks.
    However:

    there’s no such thing as a random sample of all the numbers

    This is wrong. There is no UNIFORM random sample of all the numbers. But you can easily construct random samples of real numbers, or integers, or any set you want, be it finite, infinite, countable or uncountable.

    Similarly, there’s no such thing as a randomly-chosen function out of all the possible functions.

    This is complicated, since the set of “all the possible functions” is ill-defined. But if I assume you’re talking about functions in “usual” functional spaces, you’re wrong. Most of the “usual” functional spaces admits a basis, and you can therefore built a randomly-chosen function just by chosing a linear combination of the basis functions with random coefficients. Yet again, there is no UNIFORM randomly-chosen function out of all the possible functions. Generally speaking, there is no uniform random sample of any infinite set.

  9. Pingback: Party Opponent

  10. Hey

    I thought this was supposed to be fun

    :(

    My friends (including a couple of economists and a biology PhD) aren’t happy. I read them out the question and they thought and thought and now the answer is unflippingpossible for a normal person to understand.

    hmph.

  11. Pingback: Math Puzzle « tom

  12. I read through everyone’s comments, and right now I’m thinking that a strategy exists. In XKCDs post there was a strategy that I thought worked, but it didn’t show all the work. This is my understanding of the problem, correct me if I’m wrong…

    Let the different numbers be a and b with a < b. Let there also be a probability distribution g(x) that is continuous and defined over all the reals.

    Strategy:
    1. After the player picks is revealed a number, he generates a random number from g(x). We'll call this number g.
    2. If the number he selected is larger than the number he generated, he picks the selected number as the largest.
    3. If the number he selected is smaller than the number he generated, he picks the unrevealed number as the largest. (Selected number as smallest.)

    If he is revealed a (aa)

    If he is revealed b,

    p(wining|revealed b) = p(ga) + p(g<b))

    Since aa) = p(g>=b) + p(b>g>a)
    p(g<b) = p(g<=a) + p(a<g
    =b) + p(b>g>a) + p(g<=a) + p(a<g=b) + p(b>g>a) + p(g<=a)) + 1/2*p(a<g<b)
    = 1/2 + 1/2*p(a<g<b)

    Which is greater than 1/2.

    I think this works, did I miss anything?

  13. Hmm, that isn’t what I submitted..

    The line of that equation is correct, but none of the other work is…

  14. What is displayed isn’t what I submitted…

    The last line of that equation is correct, but none of the other math.

  15. For those who are complaining about 0 being special, just change it to this:

    p(x)=1/(1+e^-(x-m))

    …where \m\ is a mean of observed numbers calculated in some suitable way. In addition to removing the complaint of 0 being special, this will end up being more accurate if the actual mean is not 0.

  16. Assuming that we find out whether our guesses are right or wrong, the general solution is to model the distributions of the numbers determined to be \lower\ and the numbers determined to be \higher\. One would then use these distributions to make guesses.

    If Alice’s process draws the higher and lower numbers from the same distribution, then both distributions will be the same, and the solution will devolve into a single-distribution case.

    If Alice’s process is not easily modeled by whatever distribution we are using, it will devolve into the initially proposed solution, which simply relies on the fact that the distribution cannot be uniform over all real numbers.

    We could even use the initially proposed solution until our model got good enough to consistently outperform it, so as to avoid making very bad guesses for a while due to low sample size.

  17. This is pretty fascinating. Before looking at the answer I thought I had proved that there was no such process. But I had assumed that the algorithm had to be deterministic, i.e. with no randomness. My argument is as follows:

    Given an deterministic algorithm to decide which of the two numbers is larger, we associate with each real number x on of two outputs “greater” or “smaller”. Then for this algorithm, Alice can pick two particular numbers that both result in the same output. Then when she picks one at random you only have a 50% chance of being right. So for each deterministic algorithm, you can pick two numbers so that it won’t work.

    So it seems that the random element in the algorithm to decide which number is higher is necessary. The method for choosing a number between 0 and 1 has to be truly random, no pseudo-random process using the number in the first envelope as a seed will work. For example, suppose you decide to take the number in the first envelope and cut out the first thousand digits after the decimal point to make a new number between 0 and 1, and use that as your random number. I think this would work fine if Alice chooses her two numbers according to, say, a normal distribution. However if she’s prescient and she knows your algorithm, she can just pick two numbers that are the same after one thousand digits past the decimal so that your “random” algorithm will pick the same result no matter which of the two numbers it is given, thus giving a 50% chance of your being correct.

  18. Alice can win this game every time by choosing identical numbers, and every time you guess higher or lower you’re wrong!!!

    …Okay, I know this doesn’t really contribute to the conversation….just saying…

  19. I’m not a math guru, I’m a common sense kinda guy. Sometimes I don’t get certain XKCD strips, and it’s a little bothersome. But I do enjoy things like this, even if I can’t do the math and didn’t study statistics.

    I’ve love to hear a down to earth explanation as to why the quantity of possible larger numbers is not always equal to the quantity of possible smaller numbers, since both are infinite.

    The only thing I can reason is that since “infinity” and “negative infinity” are not legal choices, the quantity of possible larger and smaller numbers is also not infinite. Therefore, picking lower if you draw a positive number, and picking higher if you draw a negative number, should in fact result in a winning strategy.

  20. sure. depending if the real first is positive/negative, pick the second number being greater/less determined by on the initial number’s value relative to zero. If it’s less than zero, it’s greater, and vice versa.

    If you were to plot enough data points over long enough time, there would be an increase in likelyhood you get it correct, as there will be ever-so-slightly more opportunities for the second number to fall within your range you picked, relative to the placement when compared to zero. 50.000000000000001% is still greater than 50%.

    BUT–

    If the initial number is zero… then take a shot of vodka. :)

  21. Assuming an unlimited range of numbers, then you should always answer ‘larger’ since no matter what number is contained in the first envelope, there are a finite set of numbers between 0 and the number, and there are always an infinite set of numbers greater than it.

  22. The real numbers are not “centered” at 0! (that’s an exclamation point). There are exactly as many to the right of any given point as to the left, no matter where you are. The problem with simulation is that we are substituting a finite set of integers for reals, and of course in that case the number of points to either side of some random point is not always equal, and thus our guess can improve on .5.

    “(although if she picks two particularly large positive or negative numbers, the difference is probably too small to measure).”

    The ratio of “particularly large” numbers to the rest is infinite, no matter how you define “the rest” (unless you get very cute about it). This “difference” (between your success and .5) goes to zero as the chance of a “particularly large number” goes to infinity; since she has all reals to choose from though, this difference is exactly zero (since the ratio of particularly large numbers to all others goes to 0 as our interval increases).

    Incidentally, the fact that the real line is homeomorphic to the unit interval (via the logistic function, stereographic projection, or whatever) only serves to magnify our mistaken intuition. If you asked her to choose a real number between 0 and 1 at random, and then saw that she had chosen .999, you still would do no better guessing “less” than “more” for the second number. There are the same number of reals in either interval ( [0,.999] and [.999,1] ), and thus both have a .5 probability. Any other results you get via simulation/intuition are simply because your computer/brain has way, way too few points to work with.

  23. @JD – Oops – yeah, missed ‘any real number’ and was thinking positive only after reading some of these values.

    some very good points in your comment

  24. >Choose a random real number between 0 and 1.

    This cannot provide information about any other random event, and completely pointless. Introducing a 2nd experiment is an odd way to solve a probability problem. I think it just let your mathematics become “equal”.. equally broken on both sides, so equal ? :)

    Your function p(x) may be monotonic, but it does not correctly map probability distribution from the range of 0 to 1 to -inf to inf. Well it is one map, but you chose it arbitrarily. it does produce a probability distribution and that means it does not represent -inf to inf.. there can be
    no such distribution calculated and so any calculable distribution you define must be wrong.

    You already agreed the game is impossible, which goes hand in hand with the probabibility distribution not being calculable, definable.

    If you restrict the random real number to being inside a certain range “mostly” then you have really got a roullette board, only sometimes does it spit out 37 and cancel all bets.

  25. xkcd provides a certain workable probability distribution over -inf to inf, by providing linear range for the range over 0 to 1 and then a mapping between the two ranges.

    Two problems

    1. this changed the rules
    2. it changed the rules to a playable game, which is not consistent with the known fact the original game is not playable.
    3. it was arbitrary, there are infinitely many possible probability distributions to use .. there was no proof this was the one true probability distribution.

    really the original problem didnt say what the probability distribution over the range -inf to +inf should be. but xkcd said the original game was impossible, which means that the probability distribution was also impossible to determine.

    4. Its not a paradox because the game cannot be played… no paradox that we get stupid results from analyzing an unplayable game.

    5. Someone else provided the strategy: if the first envelope is positive the 2nd envelope is likely to be smaller (because the lower side is bigger.. and vica versa. yes great strategy .. The same loigic gives the the benefit of using this strategy . you can win 0.00000000000000000(etc)1% more games…

    Thats just another result of the impossibility of having that linear distribution :). It was an impossible game, so there is no strategy to be best at it.

  26. I think that there is no solution (mathematically). Consider:

    The range of playable numbers is reals in the range of inf to -inf.

    No matter what number is chosen first, there are still infinity choices greater than that chosen number, and infinity choices less than that chosen number.

    That is why the ‘partition at 0′ solution is untenable — inf / x = inf.

  27. Easy:

    If the number is positive, guess that the other number is less than this.

    If the number is negative, guess that the other number is more than this.

    :P

  28. assume you can only write a limited number of characters onto the letter (like in reality). for example 4.
    the smallest number would be -999 and the largest 1000.
    there is also a limitation with decimal digits: -9.9 to 99.9

    this means there are more positive than negative possibilies…

  29. May be i’m very stupid but…

    i would say:

    - if the first is negative >>> next positive
    - if the first is positive >>> next negative

  30. My statistics professor once told me that probability by definition only applies to future events; thus, there is no probability involved on Bob’s behalf; he either guesses right or he doesn’t.

    That said, I think the flaw is in the definition.

  31. Suppose Alice picks numbers as follows:
    0. Keep a fixed positive number A in mind
    1. Pick a number x by some process (from -infinity to + infinity)
    2. Put in the envelopes the numbers x+A and x-A.

    Of course, you don’t know this. Second, since only an independent auditor opens the second envelope, and merely tells you whether you were right or wrong, you never come to know this.

    The proposed solution suggests you can still beat 50%. Intuitively seems to me that you cannot.

  32. Sorry, you’re just wrong.
    “II 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.” ”

    Nope, you’re dead wrong. Suppose you supply a “solution” (it doesn’t matter what the “solution” is). I can now trivially construct a process for Alice to use to choose real numbers such that your solution fails.

    Underspecified problem.

  33. To clarify:
    “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?”
    No, there is not. For any strategy you choose, there is a procedure Alice can use such that your strategy gives you no better than a 50% chance of guessing correctly.

    If you ask the question “”Is there a strategy which gives you a better than 50% chance of guessing correctly given that you do not know how Alice picked her numbers?”, and you’re a Bayesian statistician, then you may be able to find such a strategy.

  34. I think this is just a poorly defined problem. Wouldn’t the solution not hold up if Alice’s process was pick a number, then pick 1 or -1 and add it to the first number to get the second number? Or any other process where one was chosen, then it boils down to 50% chance of making the second larger or smaller than the first?

  35. Quite a few people here have hit on the basic principle. When the problem is stripped down to its basics, the tacit assumption is that when Alice ‘picks a real number at random’, she will by symmetry pick positive numbers and negative numbers with equal frequency.

    In which case, the simple strategy of guessing ‘lower’ for any positive number and ‘higher’ for any negative number (and making an arbitrary choice for zero) will succeed with a long-term frequency strictly greater than 50%. Randall’s original strategy using the logit function is just a more highfalutin way to achieve the same result – like the simple sign-based strategy, it has a propensity to generate the answer ‘lower’ for positive numbers and ‘higher’ for negative numbers.

    As has been pointed out, Alice can in fact defeat both the simple strategy and Randall’s more complex strategy by sampling real numbers from a random process with a mean value different from zero. The easiest way to do this is to always pick pairs of positive numbers – for definiteness, given them a uniform frequency distribution between 10 and 20. The sign-based strategy will then always answer ‘lower’ (and be correct no more than 50% of the time), and Randall’s strategy will answer ‘lower’ with greater than 50% frequency, and will likely be wrong more than 50% of the time.

    In short, without understanding at least something of how Alice is deciding what real numbers to pick, there is no strategy guaranteed to give you an advantage.

  36. Flip the coin again, and if you get what you got the first time you read the envelope you already opened (you lsoe) but if you get the other side of the coin you get to open the other envelope (you win). :p

  37. I’m not quite sure about this one. I think that the answer should be “No”. Let me think about the consequences of being able to find a strategy that gives you better than 50% to see if I reach a contradiction

  38. Pingback: KenKen – Online Puzzle Game

  39. I don’t know if this was said before, but there’s another solution. I don’t think it’s more accurate, it may be worse, but it’s a lot easier to remember.

    You take a random number between 1 and the number that was chosen. If the number picked is 1, go higher. Otherwise, go lower. The chance of success is equal to .5(1+(1/(ab))), where a and b are the numbers in the two envelopes. For an a of 100 and a b of 200, this chance is almost insignificantly larger than .5, but it still is.

  40. On second thought, my chance of success was completely off. Let’s say a is the larger of the two numbers. The chance is then .5(1+((a-b)/(ab)). You’re going to get nearly a half chance of getting it right if you pick the larger number, and a very low chance if you pick the smaller number. But it still works.

  41. I know this has sorta died but thought i should mention any way.
    all the solutions require you to be able to quantify were in the linear scale of real numbers a given number is and selecting the sub set with more numbers.
    but real numbers are uncountable this results in us not able to quantify the position of a given number in the set let alone the sub set with more numbers.
    there for there is always a 50/50 chance that a number will be higher or lower.

  42. da_monkey that is under the assumption that the two can be the same, and more specifically that you can guess they are the same. If you assume that one number is larger than the other number, then you are able to create methods that are greater than 50% success.

  43. I think the only real (no pun intended) problem here is that many people are assuming that for a positive number there are more numbers which are smaller than it.

    Think of googol^googol (that’s a hell of a big number). Let’s call it G. It’s finite (hell big but finite). I know this is counterintuitive but there are as many real numbers x so that x G.

    The real number line is infinite, no matter which point you choose in it, the size to the left is EXACTLY equal to the size to the right

Leave a Reply

Your email address will not be published. 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>