Maths Olympiad Prep

Library / /193 of 196

Combinatorics Difficulty 7.1 National Olympiad, round 2 Prove it Soviet Union

Problem:

Two players alternately choose the sign for one of the numbers 1,2,,201, 2, \ldots, 20. Once a sign has been chosen it cannot be changed. The first player tries to minimize the final absolute value of the total and the second player to maximize it. What is the outcome (assuming both players play perfectly)?

Example: the players might play successively: 11, 2020, 19-19, 1818, 17-17, 1616, 15-15, 1414, 13-13, 1212, 11-11, 1010, 9-9, 88, 7-7, 66, 5-5, 44, 3-3, 22. Then the outcome is 1212. However, in this example the second player played badly!

Solution

Solution:

Answer: 3030.

The second player can play the following strategy:

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

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

(3) If the first player plays 1919 or 2020, then he plays the other with the same sign.

This secures a score of at least 3939 (from (3)) less 9×19 \times 1 (from (1) and (2)). So he can ensure a score of at least 3030.

The first player can play the following strategy:

(1) He opens with 11.

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

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

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

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

Now suppose that the second player plays 2020, a1a_1, a2a_2, \ldots, ana_n (where 1n91 \leq n \leq 9) which require a reply under (4). The reason a1a_1 required a move under (4) was that a11a_1 - 1 or a1+1a_1 + 1 was the 1st player's response to 2020. Similarly, the reason a2a_2 required a move under (4) was that a21a_2 - 1 or a2+1a_2 + 1 was the 1st player's response to a2a_2, and so on. Thus the increment to the absolute value from these moves is at most 20a1+a1a2++an1an+an=20+n|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 (9n)×1(9 - n) \times 1, and the increment from the move under (1) is 11. Hence the maximum absolute value is 3030.

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.