Source: P. Winkler
I write two different numbers in the range [a,b], one on each hand. You choose one of my hands at random, I show you the number on that hand. You now guess whether the number you've seen is larger than the number you haven't seen.
Find a strategy for guessing such that, no matter what two numbers I write, you have GREATER THAN a 50% chance of being correct.
Highlight the part between the * symbols for the answer.
* I would choose a number randomly in the range [a,b]. Add 0.5 to it and save the number as k in my memory. If the number I see in one hand is less than k, I would say that the number in the other hand is greater. In the other case, I will say that the number in the other hand is less.
One can prove that here, winning probability is greater than 0.5
Let the number that comes out is k'
If k' less than k,
I am doing well when other number is either greater than k or between k' and k
If k' greater than k
I am doing well when other number is either less than k or between k' and k
So, the probability is greater than half, though getting an epsilon is not possible.
Answer :) *
Update(05/02/10): Thanx to Aaditya Ramdas for pointing out a "mistake" in the problem (discussion in comments). Problem statement changed slightly and is correct now. :)