4
$\begingroup$

Consider the following interesting puzzle:

"Alice writes two distinct real numbers between 0 and 1 on two sheets of paper. Bob selects one of the sheets randomly to inspect it. He then has to declare whether the number he sees is the bigger or smaller of the two. Is there any way he can expect to be correct more than half the times Alice plays this game with him?"

SPOILER ALERT: In the linked site below, the solution to this puzzle is right below the posed question.

The puzzle is lifted from here.

In the following questions, I have just given my hunch. My calculations could be wrong as I am not very strong at probability.

Questions:

1) Is there an assumption here that Bob can play the game many times with Alice (from the last statement)? Are the real numbers assumed to be fixed? My hunch: If it is played in time, then fixed real numbers dont make sense. So perhaps we have to think over different realizations. Is this right?

2)[Variant] If Bob knows that Alice samples the two real numbers uniformly and independently from [0,1] every time she plays then can he design a strategy that works more than half of the times? My opinion: I have a strategy that works two-thirds of the time. However I am not sure if that is the best! Is there a strategy that works better?

3) Is there a distribution from which if Alice samples her numbers independently, then she can ensure that Bob can never do better than getting right half the time? My opinion: No! Although I am not sure. I guess the independence assumption is what allows Bob to get a good strategy.

4) If Alice can sample two real numbers in a correlated fashion every time she plays, can she ensure that Bob can never do better than getting right half the time? My opinion: Yes! I think I have an answer.

P.S: I will post my version of the answers after a few days, if nobody comes up with the same idea. Thanks! :)

P.P.S: This is not a homework problem, but just a musing :)

  • 0
    The source in the link says 2000-2002, but I got this puzzle in my math class in 1998 (I know for sure because I started and quit my math study in 1998).2018-05-20

2 Answers 2

2

1) That's not well-specified in the formulation of the problem.

2) You can attain $3/4$ by choosing the first number iff it's above $1/2$.

3) No, she can't but that has nothing to do with independence; see 4).

4) No, she can't; see the links in my comment under the question.

  • 0
    @joriki ok, then I interpreted question 1 differently.2018-07-03
0
  1. If the real numbers are drawn from a fixed and finite set known to Bob, i.e. Alice picks $x,y$ with $x,y \in S $ where $S$ is a finite set, he can win whenever he chooses the minimum or maximum element of $S$. If Alice draws at random from $S$, Bob can win more often than not by setting a threshold at the median of $S$. On the other hand, if $S$ is an infinite set, e.g. the rationals in $(0,1)$, and Alice picks from this set, Bob cannot use this strategy because $S$ has no smallest or largest element, nor does it even have a median.

  2. If Alice samples i.i.d. from $U(0,1)$, by symmetry Bob should set a threshold at $0.5$. Then Bob should win with probability $p = \frac{3}{4}$ as per Joriki's answer.

  3. I don't think so, but am not sure.

  4. Alice first picks a number $x$ distributed as $x \sim U(0,1)$. Then she should write the two numbers $x - \epsilon, x + \epsilon$ where $\epsilon > 0$ is made as small as Alice wants, so that Bob gains no information from knowledge of one of the two numbers. If $\epsilon$ is sufficiently small, Bob can only guess correctly with probability $p = \frac{1}{2}$, i.e. $p \rightarrow \frac{1}{2}^+\text{ as }\epsilon \rightarrow 0^+$.