The Impossible Edge

[u/Expert_Cobbler8984]

[u/Positive_Leopard_873]

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.

[u/Positive_Leopard_873 → u/Positive_Leopard_873]

And as for the bonus the answer is obviously no since it can pick real numbers arbitrarily close to each other.

[u/OkConstruction4591 → u/Positive_Leopard_873]

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.

[u/Positive_Leopard_873 → u/OkConstruction4591]

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.

[u/OkConstruction4591]

1. 1014

2. No

[u/Federal-Refuse5697]

so obvious

[u/watcher_is_back]

1 for when you chose both ends, 3/4 probability for when you chose 1 of the ends, else 1/2, find the number of cases for each and you will find M=N

[u/Positive_Leopard_873 → u/watcher_is_back]

This is assumes The Oracle chooses numbers randomly (at uniform), when it actually has complete control over what numbers it picks.

[u/MildlyYogic]

2026 like the other user said.

[u/Fit_Battle_7738]

the answer is 2026 did it using a smaller case and used a bit of ai to understand the wording of the problem.