ROB selects A and B. First suppose A < B. Suppose A is revealed. Further Suppose that some deterministic Algorithm R exists which takes in A, and produces the probability that A is smaller.
In round one the only input to the algorithm can be A alone. Furthermore since we have supposed that R is “better than 50%”, we must see have R yield us that P( A smaller ) > 0.5. We can then easily extrapolate P( A bigger ) < 0.5.
Now suppose we have the opposite case, that A > B. Again the only input to our algorithm can be A for the first round. However we must receive as output: P( A smaller ) < 0.5 and thus P( A bigger ) > 0 5
But consider that in both cases our only input was A, then it follows that R must not be deterministic since it produces two different results on the same input. This is a contradiction, hence there is no such deterministic algorithm R.
It is possible that there is a nondeterministic algorithm R’, however I’m almost certain that no such algorithm can outperform a deterministic one in a case like this.
I’m very interested to see the solution to this problem. I agree that “better than 50%” is a little vague, however even with the most generous interpretation I’m skeptical about the existence of such an algorithm, as long as we allow the nunbers to be arbitrarily selected.
Consider the following strategy. For N rounds of play, before round 1, let ROB arbitraily select a list of N numbers. For each round let ROB choose arbitrarily one member x of the set as A, remove that member from the list, and select B as x+1.
Clearly each round is independent since the selection of each round’s numbers did not depend on the previous round in any respect.
For the first round, it’s clearly impossible to produce an algorithm which gives a better than 50% chance of success. Since subsequent rounds are independent, the same conclusion holds.