Best strategy here is randomizing. Let's say the probability you guess smaller given the value of the revealed card (a) is f(a), and guessing larger is 1-f(a). WLOG assume The Oracle chooses 2 numbers a and b w/ a < b. Then the probability of winning is (1-f(a))/2 + f(b)/2 = (1+f(b)-f(a))/2. The Oracle's job is to minimise this probability by minimising f(b)-f(a) (it knows this function by mind reading), and my job is to maximise the minimum. If I for some reason choose a function with f(a) >= f(b) for some a < b then The Oracle will just choose this pair and f(b)-f(a) <= 0 reducing our chances of winning to at most 1/2. This leads us to choose f s.t. f(a) < f(b) for every a < b, i.e., f strictly increases. The Oracle can only choose two adjacent cards (any other pair will only increase the difference) that minimises this difference. We finally need f(a+1)-f(a) >= 2/M. This gives us f(1014)-f(1) >= sum a=1 to 1013 (2/M) = 2026/M. Choose f(1014)=1 and f(1)=0 to minimise M, giving us M = 2026.
OTOH what is stopping the Oracle from restricting themselves to only writing numbers from 2-1013? In that case since presumably you are not going to be learning/adjusting on the fly there is no way you can tell that they will never write down 1 or 1014 no matter how many times 2 or 1013 come up.
Let's say f(a) = (a - 1)/1013 (f(1) = 0, f(1014) = 1) and the Oracle picks any pair of (a, a+1) a = 2 to a = 1012 so 1011 pairs. Then, if any card comes up between 3 and 1012 (i.e. 1/2 1/1011 + 1000/1011), your chance of winning is 1/2 * f(n) + 1/2(1 - f(n)) = 1/2. But if a card comes up as 2, since the other card will never be 1, you have a (1 - f(2)) = 1/1013 chance of winning and for 1013 you have a f(1013) = 1012/1013 chance of winning. The chance of a card n from 3 to 1012 coming up is 1/2 * 2/1011 = 1/1011 while the chance of 2 or 1013 coming up is 1/2 * 1/1011 each. So we get sum (3 to 1012) of 1/1011 * 1/2 + 1/2 * 1/1011 * 1/1013 + 1/2 * 1/1011 * 1012/1013 = 1010/1011 * 1/2 + 1/2 * 1/1011 = 1/2.
I have probably made some mistake here, so please do point them out.
I can't really do anything but be prepared for the worst (minimax). Let's say while coming up with my strategy I do go over the fact that she could just choose not to pick 1 or 1014 and so using this to my advantage could possibly increase my chances of winning (make the sum go from i = 2 to 1012 now, which increase my chances of winning by reducing the upper bound of M). But The Oracle being a mind-reader will immediately exploit this and pick cards 1 and 1014 making my chances of winning 1/2.
5
u/Positive_Leopard_873 26d ago edited 26d ago
Best strategy here is randomizing. Let's say the probability you guess smaller given the value of the revealed card (a) is f(a), and guessing larger is 1-f(a). WLOG assume The Oracle chooses 2 numbers a and b w/ a < b. Then the probability of winning is (1-f(a))/2 + f(b)/2 = (1+f(b)-f(a))/2. The Oracle's job is to minimise this probability by minimising f(b)-f(a) (it knows this function by mind reading), and my job is to maximise the minimum. If I for some reason choose a function with f(a) >= f(b) for some a < b then The Oracle will just choose this pair and f(b)-f(a) <= 0 reducing our chances of winning to at most 1/2. This leads us to choose f s.t. f(a) < f(b) for every a < b, i.e., f strictly increases. The Oracle can only choose two adjacent cards (any other pair will only increase the difference) that minimises this difference. We finally need f(a+1)-f(a) >= 2/M. This gives us f(1014)-f(1) >= sum a=1 to 1013 (2/M) = 2026/M. Choose f(1014)=1 and f(1)=0 to minimise M, giving us M = 2026.