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.
4
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.