6th ASU 1966 Problem 12 Two players alternately choose the sign for one of the numbers 1, 2, ... , 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: 1, 20, -19, 18, -17, 16, -15, 14, -13, 12, -11, 10, -9, 8, -7, 6, -5, 4, -3, 2. Then the outcome is 12. However, in this example the second player played badly! Solution
: 30. The second player can play the following strategy: (1) if the first player plays 2n-1 for 1 <= n <= 9, then he replies 2n with the opposite sign; (2) if the first player plays 2n for 1 <= n <= 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 x 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 ≤ n <= 9, then he replies with 2n+1 with the opposite sign; (3) if the second player plays 2n+1 for 1 <= n <= 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 x 1 (from (2) and (3) ) + 20 = 30. Now suppose that the second player plays 20, a 1 , a 2 , ... , a n (where 1 ≤ n ≤ 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 +1| + |a 1 -a 2 +1| + ... + |a n-1 -a n +1| + |a n | = 20 + n. The increment from the moves under (2) and (3) is (9 - n) x 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. 6th ASU 1966 (C) John Scholes jscholes@kalva.demon.co.uk 6 Nov 1998