IMO 1990 Problem B2 Given an initial integer n 0 > 1, two players A and B choose integers n 1 , n 2 , n 3 , ... alternately according to the following rules: Knowing n 2k , A chooses any integer n 2k+1 such that n 2k ≤ n 2k+1 ≤ n 2k 2 . Knowing n 2k+1 , B chooses any integer n 2k+2 such that n 2k+1 /n 2k+2 = p r for some prime p and integer r ≥ 1. Player A wins the game by choosing the number 1990; player B wins by choosing the number 1. For which n 0 does (a) A have a winning strategy? (b) B have a winning strategy? (c) Neither player have a winning strategy? Solution
Problem 887
Official solution
: if n 0 = 2, 3, 4 or 5 then A loses; if n 0 ≥ 8, then A wins; if n 0 = 6 or 7 , then it is a draw. A's strategy given a number n is as follows: (1) if n ∈ [8, 11], pick 60 (2) if n ∈ [12, 16], pick 140 (3) if n ∈ [17, 22], pick 280 (4) if n ∈ [23, 44], pick 504 (5) if n ∈ [45, 1990], pick 1990 (6) if n = 1991 = 11.181 (181 is prime), pick 1991 (7) if n ∈ [11 r 181 + 1, 11 r+1 181] for some r > 0, pick 11 r+1 181. Clearly (5) wins immediately for A. After (4) B has 7.8.9 so must pick 56, 63, 72 or 168, which gives A an immediate win by (5). After (3) B must pick 35, 40, 56, 70 or 140, so A wins by (4) and (5). After (2) B must pick 20, 28, 35 or 70, so A wins by (3) - (5). After (1) B must pick 12, 15, 20 or 30, so A wins by (2) - (5). If B is given 11 r+1 181, then B must pick 181, 11.181, ... , 11 r .181 or 11 r+1 , all of which are ≤ 11 r .181. So if A is given a number n in (6) or (7) then after a turn each A is given a number = 11), so after a finite number of turns A wins. If B gets a number less than 6, then he can pick 1 and win. Hence if A is given 2, he loses, because he must pick a number less than 5. Now if B gets a number of 11 or less, he wins by picking 1 or 2. Hence if A is given 3, he loses, because he must pick a number less than 10. Now if B gets a number of 19 or less, he can win by picking 1, 2 or 3. So if A is given 4 he loses. Now if B is given 29 or less, he can pick 1, 2, 3 or 4 and win. So if A is given 5 he loses. We now have to consider what happens if A gets 6 or 7. He must pick 30 or more, or B wins. If he picks 31, 32, 33, 34, 35 or 36, then B wins by picking (for example) 1, 1, 3, 2, 5, 4 respectively. So his only hope given 6 is to pick 30. B also wins given any of 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 48, 49 (winning moves, for example, 37, 1; 38, 2; 39, 3; 40, 5; 41, 1; 43, 1; 44, 4; 45, 5; 46, 3; 47, 1; 48, 3]. So A's only hope given 7 is to pick 30 or 42. If B is faced with 30=2·3·5, then he has a choice of 6, 10, 15. We have already established that 10 and 15 will lose, so he must pick 6. Thus 6 is a draw: A must pick 30 or lose, and then B must pick 6 or lose. If B is faced with 42=2·3·7, then he has a choice of 6, 14 or 21. We have already established that 14 and 21 lose, so he must pick 6. Thus 7 is also a draw: A must pick 30 or 42, and then B must pick 6. Comment I am grateful to Gerhard Wöginger and Jean-Pierre Ehrmann for finding errors in my original solution. Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X. 31st IMO 1990 © John Scholes [email protected] 22 Nov 1999