Confusing riddle problem

SydneyBristow · #1 $Old$ October 27th, 2009, 07:51 AM

Not sure where to start- this is more of a riddle our proff asked, but now i am bothered by it and want the answer.

I know two distinct secret numbers: call them X and Y , and assume that X < Y , without loss of generality. You have no clue how I came up with them. They could be anything (positive, negative, rational, irrational, etc). They could come from any probability distribution (discrete or continuous). You have no idea. I flip a fair coin. If the coin shows Heads, I reveal to you the larger number, Y ; if it shows Tails, I reveal to you the smaller number, X. You do not get to see the result of the coin flip. Your goal is to guess whether the coin was Heads or Tails, based only on your seeing the one number that I revealed to you. Obviously, if you just decide “Heads” is your guess, without taking into account the revealed number at all, then you are correct with probability 0.5. But your goal is to be able to be correct with probability strictly greater than 0.5. Devise a method to do this, and explain your solution.

theodds · #2 $Old$ October 27th, 2009, 01:44 PM

I think this works, but put a big disclaimer on it:

The number is revealed; call it Q. Calculate $P = \frac{Q}{Q + 1}$ . Now, flip your own coin, with weighted probability P of heads. If heads is revealed, then you guess that Q is the larger of the two numbers (i.e. call "heads"). It should work out that your probability of guessing right is:

$\frac{1}{2} + \frac{1}{2} \left ( \frac{Y}{Y + 1} - \frac{X}{X+1} \right )$ , but since the term associated with Y is strictly larger than the one associated with X (because Y is bigger), you will win with a probability greater than 1/2.

EDIT: LOL, this doesn't work for negative numbers, but maybe you can tweak it using a similar method. I think the main step to take in solving this is to have a switching probability based on the number revealed, and devise a way for it to make you switch away from the smaller one more frequently than the larger one.

theodds · #3 $Old$ October 27th, 2009, 03:41 PM

Okay, updating my last post with a solution that works for numbers on the whole real line.

The number is revealed, call it Q. Then, let

$P(Q) = \frac{arctan(Q)}{\pi} + \frac{1}{2}$

and call "heads" with probability P(Q) - you can verify for the whole real line that P(Q) is a valid probability, and I'll leave it to you to figure out where I pulled P(Q) from, and it should also give you plenty different examples of functions that will work [Hint: all we need is a function that maps R into (0, 1) that is strictly increasing...and such functions are particularly common in probability theory]. Your probability of winning the game will now be

$\frac{1}{2} + \frac{1}{2}[P(Y) - P(X)]$

which is strictly greater than .5 because if Y > X, then arctan(Y) > arctan(X).

Laurent · #4 $Old$ October 28th, 2009, 05:55 AM

Here is another way to explain the exact same solution.

In full generality, what we need to find is a function $p:\mathbb{R}\to[0,1]$ that will describe our way to answer: if we are given the number $\alpha\in\mathbb{R}$ , then we answer "It is Y (the larger one)" with probability $p(\alpha)$ and "It is X (the smaller one)" with probability $1-p(\alpha)$ . Note that this covers in particular the case of a deterministic answer ( $p(\alpha)\in\{0,1\}$ ), even if this is not a good choice.

Suppose we are given the number $Q$ , and that our answer (based on the above strategy) is $Z$ , which is either 1 if we say that $Q$ is Y, or 0 is we say it is X. Then the probability that our guess was correct is:

$P(Q=Y\mbox{ and }Z=1)+P(Q=X\mbox{ and }Z=0)=\frac{1}{2}p(Y)+\frac{1}{2}(1-p(X))$ $=\frac{1}{2}+\frac{1}{2}(p(Y)-p(X))$ .

As we can see, this is larger than $\frac{1}{2}$ if and only if $p(Y)>p(X)$ . However, we don't know what $X$ and $Y$ are when we choose the function $p(\cdot)$ . Therefore we have to choose a function such that $p(y)>p(x)$ for all real numbers $y>x$ . In other words, $p$ must be strictly increasing from $\mathbb{R}$ to $[0,1]$ . A possible choice of the function $p(\cdot)$ was given by TheOdds in his last post.