Two players play the following game:
Each player writes down a whole number between 0 and 100 on a slip of paper, then the players simultaneously reveal their choices. If the difference between the two numbers is at least 60, then the player with the smaller number wins, otherwise the player with the larger number wins (the game is a tie if both players chose the same number).
What is the optimal strategy for this game?
Assuming the opponent has access to our strategy beforehand and we want to provide a way to still ensure even odds, my first attempt was
To devise a simple coin toss strategy. With probability 0.5 we pick $A$, otherwise $B$.
From the graph that @DanDan0101 provided (assuming we are player $X$) we now need two columns that are exactly complementary to each other, i.e., for every value $Y$ at least one of $(A,Y)$ and $(B,Y)$ must be red.
We can see that $A=0$ and $B=59$ almost meet this criteria: If the opponent chooses any value from 0 to 58, we win by choosing 59 (i.e., at least half the time). If they had chosen any value from 60 to 100 we win by choosing 0 (i.e., at least half the time). The only issue is, that if they pick exactly 59, we lose 50% of the time but in the other 50% we only get a draw.
So instead, I tried generalizing:
Let $p(A)$ denote the probability that our strategy picks $A$. If our strategy can beat every deterministic adversarial strategy with probability at least 0.5, then it can also beats every randomized strategy with probability at least 0.5.
Let $V(X,Y)$ denote the value for player $X$, i.e. $1$ if $(X,Y)$ is red in the graph, $-1$ if it is blue, and $0$ for the black line. For a given $Y$ the expected value of our strategy should then be greater or equal to $0$, i.e. for all $Y$ we require $\sum_{X=0}^{100} p(X)*V(X,Y) \geq 0$.
To provide a visual approach, I discretized @DanDan0101' diagram and made it only 20x20 for readability.
The product $\sum_{X=0}^{100} p(X)*V(X,Y)$ (or up to 20 in this version) can be seen as a version of this diagram where every $X$-colum is stretched by a factor of $p(A)$ and each row then must contain at least as much red as it does blue. First, note that all rows in $Y=0,...,9$ contain one red cell more than blue cells. Then $Y=10$ is balanced, and finally $Y=11,...,20$ contain one more blue than red cell. Actually, we can come with a pretty simple scaling: If we remove the $X=9$ and $X=10$ column (i.e., scale them by $0$), we get the following:
Here, each row has either the same number of blue and red squares ($9$ each), or (for $Y=9,10$) even one red more than blue. Translating this back to a strategy simply means we pick any number from 0 to 20 except 9 or 10 at random. Scaling this up to the original game, we can do the same kind of analysis and find that a strategy that ensures a 50% win probability, no matter what the opponent picks. The borders of the regions are a bitt fiddely, but in general you can just remove the first column with blue on the top, and then continue removing columns towards the right until the top column has as many red as blue squares.
So the final strategy is:
Pick a random number from $0$ to $100$ except numbers in the range from $41$ to $58$.
The chance of winning then is
$\frac{42}{83}$ in the best case when the opponent picks any number from $41$ to $58$, and $\frac{41}{83}$ plus a $\frac{1}{81}$ chance of a draw in the worst case when the opponent picks anything else. If the opponent applies a random strategy, our expected chance to win is a weighted combination of the two, with the weights being the probability that the opponent's random strategy picks a number in the given range.
If you want to confirm this visually, I also made the graph for the original game:
Here is the phase diagram for the game, with player X being red and player Y being blue. Solid lines and shaded regions indicate that the respective player wins. The solid black line indicates a draw. Note that the game is symmetric between the two players, so there should be no way to force a win.
From this diagram, we may see that:
No matter what number you choose, an omniscient and adversarial opponent can always ensure their victory.
If the other player chooses their number at random, then:
Picking a number between 59-100 gives you a $\frac{59}{101}$ chance of winning, $\frac{1}{101}$ of draw, and $\frac{41}{101}$ chance of losing.
