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.

399 thoughts on “Math Puzzle

  1. Mathmo, you have missed the subtle point. It has probably been explained repeatedly but I’m not ready to go back and look at lots of answers….

    Take any two numbers. Pick one of them when you don’t know the other. How can you get a better than 50% chance to guess which is larger?

    Take any function that covers the whole domain and which increases, never staying the same and never decreasing. Use that function to figure a probability that you will declare the known number the larger of the two.

    If you looked at the smaller number x1, the chance you decide it’s larger is p(x1).
    If you looked at the larger number x2, the chance you decide it’s larger is p(x2).
    p(x2) is larger tha p(x1) because the function increases. It makes no difference how the numbers were chosen, or how likely any particular number would be chosen. All that matters is that there are two numbers were x1<x2. You could use the same approach with the integers, or the positive numbers, or the rational numbers between 2 and 5.2 . All that matters is that you know the actual domain, and that you have a function which is increasing over that domain which you can us to create an increasing probability distribution over that domain.

    That's all there is to it.

    Try a simpler example. Somebody chooses two of the 11 whole numbers between 0 and 10. Call them n1 and n2. Alice tells you n2.

    Make a function, for example p(n)=n/10. So if n2=0 you say it's smaller. If n2=1 then 90% of the time you say smaller and 10% you say larger. Etc.

    Say the numbers are 7 and 5. If Alice tells you 7, there's a 70% chance you say it's larger. If Alice tells you 5, there's 50% chance you say it's larger. You are more likely to say the larger number is larger, than to say the smaller number is larger. It doesn't matter how the numbers were chosen.

    What if you choose a different function? Maybe p(n)=n/20 + 0.5 .

    Then it's still true that the larger number is more likely to be declared larger than any smaller number. The difference isn't as large, the function isn't as efficient at picking larger numbers, but it still wins more than half the time.

    Any increasing function works. Some work better than others.

  2. Dear J Thomas

    I am not sure if you correctly read my post, I would agree it is not the most eloquently written explanation, or are just trolling me, but whatever I will bite:

    You will observe that your post does not answer the question which is:
    —–
    Given an a pair of numbers, chosen by an unknown system, one of which is shown to you, chosen at random.

    Is there a strategy which gives you a better than 50% chance of guessing correctly
    ——–
    The answer to which is, sadly, no, at the point of displaying a number with a picked other the in no guarantee whatsoever that whatever strategy you pick gives you a better than even chance of correctly guessing whether the undisclosed number is higher or lower that the known one.

    (This is very clear from a simple thought experiment 0 is shown do you guess higher or lower ?)

    HOWEVER, and this is the subtle point, You do answer a different question and that is if you cannot guarantee a strategy that wins more than half the time, can you pick a strategy that before the point outlined in the question (namely when the game is proposed) that, whilst doesn’t necessarily give a unit (1.0) chance of picking a strategy that gives you a greater than even chance of winning, does give you a greater than evens chance of doing so.

    (Which as you correctly point out can be seen at the initial stage as giving a greater than even change of getting guessing correctly )

    This is perhaps best illustrated by considering a set of 4 biased coins (2 of which have P(heads) = 0.2, 2 of which have P(heads) = 0.8) of which you must pick 3 from which one is chosen at random, to be tossed.

    Q) Can you pick the 3 you can be sure that when one is selected and tossed you can be sure P(head)>0.5

    A) NO of course not you must have picked at least 1 coin with P(heads)=0.2 and there is therefore at least a 1 in 3 chance that the coin picked will have P(head)0.5

    I hope that is a little clearer as this is one of the more interesting aspects of probability theory, which it would be a same to have overlooked

  3. not sure what happened but part of my post got cut off (or got cut off by me) but to complete the analogy:
    it is also clear that (under the same conditions):

    There is a way to pick 3 coins such that the overall probability of getting heads is greater than 0.5, AT THE START OF THE GAME

    Indeed: picking 2 of the heads biased and only 1 tails biased coins gives (in a glib sense) P(heads)=1.8/3=0.6, which is happily>0.5

  4. I do not believe there is a way that will give you better than a 50/50 chance no matter what. If we use a unknown method to chose the numbers, the method could be in theory, a truly random number generator. If that was the case there would be no actual relationship between the two numbers and I fail to see how you could produce a better than 50/50 chance when attempting to chose the larger number knowing only one of the numbers.

  5. Alice has generated truly random numbers if and only if oracles exist.

    If oracles exist, then we can consult Alice’s oracle and determine 100% certainty the contents of the envelope.

    If oracles do not exist, then Alice has not generated a truly random number. Therefore, we apply the statistical method described elsewhere in this thread.

  6. @J Thomas:
    You need a function that is positive and increasing over the entire domain, but with a finite maximum. Let the domain of strictly increasing function f(x) be (-inf, inf) and the range [0,1], and the probability that you will guess \Smaller\ equal to f(n).

    Given two numbers, n1 and n2, of which you have one and Alice has the other, you have either the smaller one or the larger one. If you have the larger one, you are less likely to guess \the other number is larger\ than if you have the smaller number; switch it around if you have the smaller one.

    Let LL be the chance that you have the larger number and guess ‘larger’ (wrong), LS, be the chance that you have the larger number and guess smaller (right) SL be the chance that you have the smaller number and guess larger (right) and SS be the chance that you have the smaller number and guess wrong.

    From the problem, SL+SS=0.5 and LL+LS=0.5 (You have an equal chance of getting the smaller or larger number.
    From the work above: LL<SL and SS<LS
    Therefore: LL+SS<SL+LS
    Therefore you are more likely to guess correctly than incorrectly.

    Strangely, I think that this works even if the function f(x) is nondecreasing on the entire length, but increasing on some portion of the length.
    Consider the case of f(x)=0 for x0. There is some nonzero chance that the number you pick is postive or negative and that the other number is nonpositive or nonnegative (respectively). In those cases, you are right all the time. In the cases where the number you pick is zero, you have a .5 chance of being right. Now consider the final case: Given two numbers, both of which are either positive or negative, the odds that you number you picked will have the higher absolute value is… 0.5, regardless of what it’s value is! (If I roll a d1000 and a d2, and pick one at random before seeing the results, I have a .5 chance of picking the die with the higher roll.)

  7. This actually wasn’t that tricky, but I must admit that my first reaction was: Keep punching Alice until she admits. Based on the fact that Alice is predominantly a female name and that she also engages in math paradoxes, statistically the chance for anyone to take her (simply on the fact that she is almost per definition a female) in a fight would be greater than 50 %. If it was a boy the tactic would be to show your breasts if your a girl or buy a gun if you are a boy (based on the assumption that 90 % of all males are straight and that less than 45 % of all males are armed themselves and/or superheroes).

    So that would qualify as an answer for the “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?” conundrum, right?

  8. Maybe I’m just an idiot, but shouldn’t you always guess that the second number will be greater? After all, there are a finite number of numbers less than the first number, but an INFINITE amount of numbers greater than it.

  9. OK, since the process for selection is unknown, as far as you know any real number can be selected. Yes, it’s not feasible for any selection process to include ALL real numbers as possible outputs, but since you do not know the selection process, no real number can be eliminated by you as a possible selection. Since all real numbers, positive and negative are included, definitionally, if the 1st number is positive, saying the other number is smaller is more likely, and vice versa. There are 2 problems with this though. 1) If the first number picked IS zero, then you will always have a 50-50 shot. 2) Since the set of possible answers is infinite, the proportion of possible answers that are farther from 0 will be infinitely larger than the number of possible answers closer to zero, so the chances that you guessed correctly is an amount infinitely small larger than 50%. An infinitely small number is approximately zero, so you have an approximately 50% chance anyway….

    Or maybe I am missing something.

  10. I have read in multiple places (such as Simon Singh’s “The Code Book”) that the most reliable way to generate a truly random number in finite time is not through any sort of mathematical function (that’s impossible), but rather by taking advantage of natural processes, especially the randomness of quantum mechanics. This method is sometimes used to generate one-time pad ciphers. Essentially, a chunk of radioactive material with a relatively short half-life is placed in a chamber that can detect escaping alpha particles with the most precision possible. A clock is set that increases as rapidly as possible until an alpha particle is detected, at which point it records the number it reached and restarts. Since the time interval between the release of each alpha particle is completely random (it’s only over time that the half-life becomes predictable), these numbers are, as far as we can tell, completely random. Of course, this only yields positive numbers, and there is finite possible precision, but it’s random enough to hold up very well in cryptography at least. Of course, it’s outlandishly expensive!

  11. I think this question is being over complicated. What it comes down to is whether or not Alice picked the number conciously or relied on a random number generator (pseudo or otherwise).

    For example, pick a number 1 through 4. Write it down. Don’t just sit there asking yourself where I’m going with this, pick a number and write it down.

    Ok, got it?

    Ready?

    Now, ask yourself, honestly, why you picked 3.

    The vast majority of people did the same thing. 1 is too bold, 4 is too demure, so it comes down to 2 or 3, and most people pick 3.

    The point is that if Alice picked a number herself, then the number she picked is predictable.

    If she left it up to a pseudo-random number generator, then over half the numbers are less than seven, sooo it would be a >50% that the number is less than seven

  12. if you are a girl. you may choosing with pisicological IQ test.!
    if you are a boy you may choosing maths Iq tests!

    Thanks for perfect share!

  13. The strategy depends on the sign of the number you get. There are no bounds to the number other then that it is real. This means the number could go out to negative infinity and positive infinity.
    Lets say you get +5,943,241. This means that there are (Infinite-5,943,241) numbers above it, and (Infinite + 5,943,241) numbers below it. Therefore, there are (5,943,241 * 2) more numbers that lie below your number than lie above it.

    So, if you get a positive number, guess that its below. If you get a negative number, guess that its above.

  14. To the writer of XKCD-could you *please* call it quits with the 3-D thing? It’s hard to read and it…um…gives me a headache. (Cough Cough)

  15. Assuming there’s an equal chance of her choosing a number that’s greater than 0 or less than 0, wouldn’t the valid solution simply be to base your response on whether the number you know is greater or less than zero? If the first number you see is > 0, you say the other number is smaller, and since there are more real numbers less than the number you’ve seen than there are real numbers greater than the one you’ve seen, by definition your chances will be > 50%

  16. A truly random number generator over R would have the property that each real is as equally likely to be chosen as any other. Such a generator cannot have a probability definition function, since p(x) = 0 for all x in R, but the integral over R of p(x) is not 1.

  17. Pingback: Evrry Day I’m Shufflin’ « keepmeproductive

  18. Sie amk. I was so sorry to hear what you were going through since November….and seeing your Monday April 4 comic – I wonder if things are better or how you’re coping up with the illness in your family. Your comic strip has made so many, many of us laugh through the years and have a sense of humor about life through our tough times, wishing you strength during yours. vay ak.

  19. If you want to wholesale, cheap and discount tory burch sandals, you should come Tory burch118 outlet store for a look. We sale blakely suede thongs, holly sandals and patent square miller sandals, our products are not only cheap but also is the best choice for you. Once you have tried our sandals on, you will not want to go to another store to pick up one. Buy a pair of sandals at Tory burch118, it is the time for you to release your feet and show your nice toes.

  20. Pingback: Dominant Random Strategies: Why Judges Should Flip Coins – blog.silviupitis.com

  21. Pingback: Let’s do some math « Suhaimi Ramly

  22. On the other hand, I’d say there is a sure way for Alice to win this little game. Simply pick two complex numbers, with both imaginary and real part. Neither can be said to be either larger or smaller than the other. For extra points, make sure they have the same absolute value, too.

  23. There’s a subtle flaw in the very clever solution. You can’t select a number from a flat distribution over the set [0,1] because it’s an infinite set. You have to generate a finite set in that domain, which can be arbitrarily large and evenly distributed, but still finite. When Alice puts X in one envelope and X+1/X in the other, the difference in the logistic functions p(X) and p(X+1/X) becomes small with large X. Regardless of how finely you bin the set [0,1], there is some X that Alice can choose so that the probability of picking “higher” or “lower” using the proposed procedure does not depend on which envelope you’ve opened.

  24. This puzzle and its “solution” are obviously bogus, as indicated by several commenters. Why is this misinformation still online after 3 years? I wonder…

  25. For those still doubting in any way, the easiest way to explain why it can’t be done:

    Say x, element of reals, is the number in the envelope. Since y, element of reals, is the other number, is not equal to x, it is either in the interval (-infinity, x) or the interval (x, infinity); both intervals are open on both sides. These intervals have the same cardinality as the continuum, regardless of x, as they are both open intervals in R (reals): so they also have the same cardinality as each other. End of story.

    Probability theory is totally irrelevant to this non-puzzle, despite the mention of the ‘randomly chosen numbers’.

  26. Just thought of another pathological way to illustrate the matter in which our intuition fails here:

    Say, we know the real x from envelope 1. Let epsilon be a positive real number, however small you like. If you were to guess that the other number, y, from envelope 2, was in the set [x - epsilon, x + epsilon] \ {x}, (union of intervals [x - epsilon, x) and (x, x + epsilon]), this would still be as likely as guessing it wasn’t, for any positive epsilon you could choose.

  27. Legendary Half-Life comes to big screen! Fresh news about most famous games movie.
    First rip alredy done – 123 minutes. Not in best quality now, but with Gordon Freeman, shotgans, Black Mesa and other HL staff.
    Be First and see Half-Life movie online!!

    Released by PirateBy team.

    Short cinema-story:
    Half-Life is a science fiction video game developed by Valve Corporation, the company’s debut product and the first in the Half-Life series. First released in 1998 by Sierra Studios for Windows PCs, the game was also released for the PlayStation 2; Mac OS X and Linux ports became available in January 2013. In Half-Life, players assume the role of Dr. Gordon Freeman, a theoretical physicist who must fight his way out of a secret underground research facility whose research and experiments into teleportation technology have gone disastrously incorrect.
    Valve, set up by former Microsoft employees, had difficulty finding a publisher for the game, with many believing that it was too ambitious a project. Sierra On-Line eventually signed the game after expressing interest in making a 3D action game. The game had its first major public appearance at the 1997 Electronic Entertainment Expo. Designed for Windows, the game uses a heavily modified version of id Software’s Quake game engine with code portions from id Tech 2 engine called GoldSrc.

  28. I hate to revive an old thread, but a lot of commenters seem to have missed the point of the problem.

    The problem does NOT involve Alice telling you a single number and asking you to guess whether that number is larger or smaller than some other number she’s thought of. Obviously if this were the case, we could only hope to guess correctly 50% of the time. Plenty of people have pointed this out as if it addressed the scenario given in the post.

    The problem also does NOT involve Alice randomly picking her numbers from a uniform distribution on all reals. That would be impossible. Alice is free to choose her numbers any way she wants. We don’t know how she chooses them; for all we know she chooses pi and 42 every time.

    The problem DOES say that we have exactly a 50% chance of seeing each number. Alice doesn’t determine which number we see. A coin flip does.

    There are four mutually exclusive cases to consider:
    1) We see the larger number and correctly guess that the other number is smaller
    2) We see the smaller number and correctly guess that the other number is larger
    3) We see the larger number and incorrectly guess that the other number is larger
    4) We see the smaller number and incorrectly guess that the other number is smaller

    Since the only thing determining which number we see is a coin flip, we know that the probability of our seeing the smaller number is equal to the probability of our seeing the larger number (both probabilities are 50%). Equivalently, the probability of either Case 1 or Case 3 happening is 50%, and the probability of either case 2 or Case 4 happening is 50%.

    Our goal is to make the probability of either Case 1 or Case 2 (the cases in which we guess correctly) happening greater than 50%.

    If we follow the method laid out in the solution, Case 1 is more likely than Case 4. This is because the larger the number we see, the more likely we are to guess that the other number is smaller.

    Similarly, Case 2 is more likely than Case 3.

    Since we’re more likely to be in Case 1 than Case 4 and more likely to be in Case 2 than Case 3, we can conclude that we’re more likely to be in one of the first two cases than in one of the last two.

    The only subtle correction to make to the proposed solution is that it is not possible to choose a random real number in the interval zero to one. Fortunately, we don’t need to. All we need is a way of deciding whether to guess that the other number is larger or smaller based on the the value of the logistic function (or any other monotonically increasing function whose domain is the reals and whose range is finite) applied to the number we saw from the envelope. One way of doing this would be to repeatedly randomly sample from the discrete uniform distribution of integers from zero to nine, thereby building a decimal value between 0 and 1. We could stop this process as soon as the number we had built differed at some decimal point from the number obtained by applying the logistic function to the number from the envelope.

    For example, say Alice chose pi and 42. We happen to open the envelope containing pi. We apply the logistic function and get 0.9585…. Then we start building our random number getting 9, then 5, then 2 for 0.952. This differs from 0.9585… at the third decimal place, so we stop and say (incorrectly) that the other number is smaller. No need to actually select a random real from the zero to one range.

    If anyone is thinking that this looks bad, because we’d guess that Alice’s other number is smaller than pi about 96% of the time, remember that we are equally likely to have seen Alice’s other number, 42. By the same rules, we would guess that 42 was the larger number about 99.9999999999999% of the time. Whichever envelope we get, we’re highly likely to say that the other number is smaller.

    To apply the four cases above to this specific example, we have about a 49.9999999999% of seeing 42 and correctly saying that it’s the larger number. We have a little over a 2% chance of seeing pi and correctly saying that it’s the smaller number. This gives us a better than 52% chance of being right.

  29. Pingback: Two real numbers | Chaos at the Sky

  30. Podemos manejar cualquier trabajo al aire libre o de interior a partir de mediciones, movimientos gráficos, licencias, producción, transporte, instalación, desmontaje y mantenimiento basados ​​en nuestro conocimiento adquirido con los años y el equipo necesario.

  31. Since the only thing determining which number we see is a coin flip, we know that the probability of our seeing the smaller number is equal to the probability of our seeing the larger number

  32. Por otra parte, yo diría que es una manera segura de Alice para ganar este juego. Sólo tiene que elegir dos números complejos, y parte a la vez imaginaria y real. Ni se puede decir que ser mayor o menor que la otra. Para los puntos de más, asegúrese de que tengan el mismo valor absoluto, también.

  33. Depuis la seule chose qui déterminer le nombre que nous voyons est un coin flip, nous savons que la probabilité de voir le notre plus petit nombre est égale à la probabilité de voir notre le plus grand nombre…

  34. Cool puzzle, brilliant solution. Sorry I’m 4 years late to the party, but I think I have something interesting to add.

    First, for the non-believers, xkcd really says it all in his original solution comment. He shows that the odds of guessing correctly with that strategy will be greater than 50% for literally any pair of numbers provided by Alice, in every instance (note that the puzzle implies the game is played only once–we don’t get the luxury of guaranteeing >50 over the long haul). That means all of the concerns about the method they are chosen, or their domain, are irrelevant. Even if Alice knows your strategy, there isn’t any pair of numbers she can choose that will reduce your odds to exactly 50%.

    Another good explanation is given by jonb a few posts back. I want to address his post, because he brings up a technical problem with the solution: that it is impossible to choose a random number in the [0,1] interval. jonb offers a very good practical way around this: just generate random digits until the number differs from our p(x) value. In real life, it will be a cold day in hell before you run into a problem with this technique, but if we’re being rigorous, this plan has a flaw in that the process is not guaranteed to end within any finite period of time. I.e., choose any finite number you want, and eventually, you’ll run into a case where the process takes more iterations than that. There is, in fact, no way around this problem, as a few people have pointed out.

    This means two interesting things. (To me, anyway.)

    One is that while the answer to the original puzzle is still yes, more or less, a strategy does exist, you can’t guarantee that you’ll be able to actually carry it out.

    The more interesting thing is that if we are allowed an infinite amount of time to carry out our strategy, then we don’t need that sigmoid function at all. There is a simpler solution. We can skip that step and simply generate our very own random Real that we will compare to x, rather than comparing it to p(x). (I’m referring to the x and p(x) from xkcd’s original comment. x is the number we see in the envelope that we opened.) If our random number is greater than x, we guess that we are seeing the lower number, and vice-versa.

    Of course, it’s impossible to generate a random Real number with equal chances for all values, as several people have pointed out. However, if we are allowed an infinity of time/iterations, we can certainly come up with a method for getting any Real where the distribution is not level. For example:

    Start with “0.” and add digits to the right of the decimal using a random integer in the range [0,10]. A 10 means that we stop adding digits, otherwise add the digit indicated. Now choose random integers in the range [0,2]. Move the decimal point left if you get a 0, right if you get a 1, and stop if you get a 2. Then choose a sign for the number with a coin flip.

    Now if we graph P(r), the probability of getting any number r with our method, we see that the graph is strange (appearing to be zero in most places) and absurdly discontinuous. This may seem to be a problem at first, but actually we don’t care. The only important element is that the area under the curve is 1 (which it is) or at least finite. Now plot a different graph that is more relevant. Let L(r) be defined as the probability that for any number r, a number generated with our method will be lower than r. This is pertinent because we are comparing x to our random number r. Now here’s the magic: L(r) is both continuous and monotone increasing, for fairly obvious reasons, and from a distance it looks like a sigmoid. Zoom in, and you’ll see fractal-like ripples, but as long as it’s monotone increasing, it doesn’t matter. We have achieved our ability to guess “lower” or “higher” with a probability that will guarantee us a better than 50% shot.

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>