Math Puzzle

Posted on by

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.

388 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.

  10. 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.

  11. 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!

  12. 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

  13. 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!

  14. 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.

  15. 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)

  17. 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%

  21. 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.

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

  24. 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.

  25. 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.

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

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

  33. 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.

  34. 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.

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

  36. 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’.

  37. 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.

  38. 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.

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>