Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 amusing :)

share|improve this question
    
    
I think I saw this on mathoverflow. –  Pedro Tamaroff Aug 7 '12 at 14:42

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Thanks for the links. For the fourth part, if Alice fixes one of the numbers to, say half, and tosses a coin to pick the other number as 0.75 or 0.25. How can Bob ever get it right more than half of the time? –  Isomorphism Aug 7 '12 at 13:38
    
@Isomorphism: Did you follow the links? It would make more sense if you told me what part of the answers there you don't understand rather than me explaining everything again from scratch. You don't need randomization for this example, though -- Bob can just always accept the $.75$ and reject the $.25$ (it doesn't matter what he does with the $.5$) -- then he'll have a $3/4$ chance of winning. –  joriki Aug 7 '12 at 13:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.