Given an initial integer n0 > 1, two players A and B choose integers n1, n2, n3, ... alternately according to the following rules:
Knowing n2k, A chooses any integer n2k+1 such that n2k ≤ n2k+1 ≤ n2k2.
Knowing n2k+1, B chooses any integer n2k+2 such that n2k+1/n2k+2 = pr 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 n0 does
(a) A have a winning strategy?
(b) B have a winning strategy?
(c) Neither player have a winning strategy?
Solution
Answer: if n0 = 2, 3, 4 or 5 then A loses; if n0 ≥ 8, then A wins; if n0 = 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 ∈ [11r181 + 1, 11r+1181] for some r > 0, pick 11r+1181.
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 11r+1181, then B must pick 181, 11.181, ... , 11r.181 or 11r+1, all of which are ≤ 11r.181. So if A is given a number n in (6) or (7) then after a turn each A is given a number < n (and >= 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.
© John Scholes
jscholes@kalva.demon.co.uk
22 Nov 1999