All-Soviet-Union Mathematical Olympiad

Solution:

Answer: $30$.

The second player can play the following strategy:

(1) If the first player plays $2n - 1$ for $1 \leq n \leq 9$, then he replies $2n$ with the opposite sign.

(2) If the first player plays $2n$ for $1 \leq n \leq 9$ then he replies $2n - 1$ with the opposite sign.

(3) If the first player plays $19$ or $20$, then he plays the other with the same sign.

This secures a score of at least $39$ (from (3)) less $9 \times 1$ (from (1) and (2)). So he can ensure a score of at least $30$.

The first player can play the following strategy:

(1) He opens with $1$.

(2) If the second player plays $2n$ for $1 \leq n \leq 9$, then he replies with $2n + 1$ with the opposite sign.

(3) If the second player plays $2n + 1$ for $1 \leq n \leq 9$, then he replies with $2n$ with the opposite sign.

(4) If any of these replies are impossible, or if the second player plays $20$, then he replies with the highest number available with the opposite sign.

If the second player does not play $20$ until the last move, then this strategy ensures a score of at most $1$ (from (1)) $+ 9 \times 1$ (from (2) and (3)) $+ 20 = 30$.

Now suppose that the second player plays $20$, $a_1$, $a_2$, $\ldots$, $a_n$ (where $1 \leq n \leq 9$) which require a reply under (4). The reason $a_1$ required a move under (4) was that $a_1 - 1$ or $a_1 + 1$ was the 1st player's response to $20$. Similarly, the reason $a_2$ required a move under (4) was that $a_2 - 1$ or $a_2 + 1$ was the 1st player's response to $a_2$, and so on. Thus the increment to the absolute value from these moves is at most $|20 - a_1| + |a_1 - a_2| + \ldots + |a_{n-1} - a_n| + |a_n| = 20 + n$.

The increment from the moves under (2) and (3) is $(9 - n) \times 1$, and the increment from the move under (1) is $1$. Hence the maximum absolute value is $30$.

Since the 1st player has a strategy to do no worse than $30$ and the 2nd player has a strategy to do no worse than $30$, these strategies must actually be optimal.