Posterous theme by Cory Watilo

Filed under: math

Ez sem volt benne a függvénytáblázatban

Tupper's Self-Referential Formula
DOWNLOAD Mathematica Notebook
Tupper's formula

J. Tupper concocted the amazing formula

 1/2<|_mod(|_y/(17)_|2^(-17|_x_|-mod(|_y_|,17)),2)_|,

where |_x_| is the floor function and mod(b,m) is the mod function, which, when graphed over 0<=x<=105 and n<=y<=n+16 with

 n=96093937991895888497167296212785275471500433 
966012930665150551927170280239526642468964284217 
435071812126715378277062335599323728087414430789 
132596394133772348785773574982392662971551717371 
699516523289053822161240323885586618401323558513 
604882869333790249145422928866708109618449609170 
518345406782773155170540538162738096760256562501 
698148208341878316384911559022561000365235137034 
387446184837873723819822484986346503315941005497 
470059313833922649724946175154572836670236974546 
101465599793379853748314378684180659342222789838 
8722980000748404719,

gives the self-referential "plot" illustrated above.

Tupper's formula can be generalized to other desired outcomes. For example, L. Garron (pers. comm.) has constructed generalizations for n=13 to 29.

SEE ALSO: Self-Recursion

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