IMO 1990 SL 6

Origin: FRG

Problem

Two players A and B play a game in which they choose numbers alternately according to the following rule: At the beginning, an initial natural number n0 > 1 is given. Knowing n2k, player A may choose any n2k+1 \inN such that n2k \leqn2k+1 \leqn2 2k. Then player B chooses a number n2k+2 \inN such that n2k+1 n2k+2 = pr, where p is a prime number and r \inN. It is stipulated that player A wins the game if he (she) succeeds in choosing the number 1990, and player B wins if he (she) succeeds in choosing 1. For which natural numbers n0 can player A manage to win the game, for which n0 can player B manage to win, and for which n0 can players A and B each force a tie?

Solution

Let W denote the set of all n0 for which player A has a winning strategy, L the set of all n0 for which player B has a winning strategy, and T the set of all n0 for which a tie is ensured.

Lemma. Assume {m, m+1, . . .1990} \subseteqW and that there exists s \leq1990 such that s/pr \geqm, where pr is the largest degree of a prime that divides s. Then all integers x such that \sqrts \leqx < m also belong in W. Proof. Starting from x, player A can choose s, and by definition of s, player B cannot choose a number smaller than m. This ensures player A the victory. We now have trivially that since 452 = 2025 > 1990, it follows that for n0 \in{45, . . ., 1990} player A can choose 1990 in the first move. Hence {45, . . ., 1990} \subseteqW. Using m = 45 and selecting s = 420 = 22 \cdot 3 \cdot 5 \cdot 7 we apply the lemma to get that all integers x such that \sqrt 420 < 21 \leqx \leq1990 are in W. Again, using m = 21 and selecting s = 168 = 23 \cdot 3 \cdot 7 we apply the lemma to get that all integers x such that \sqrt 168 < 13 \leqx \leq1990 are in W. Selecting s = 105 we obtain the new value for m at m = 11. Selecting s = 60 we obtain m = 8. Thus {8, . . ., 1990} \subseteqW. For n0 > 1990 there exists r \inN such that 2r \cdot 32 < n0 \leq2r+1 \cdot 32 < n2 0. Player A can take n1 = 2r+1\cdot32. The number player B selects has to satisfy 8 \leqn2 < n0. After finitely many steps he will select 8 \leqn2r \leq1990, and A will have a winning strategy. Hence all m \geq8 belong to W. Now let us consider the case n0 \leq5. Since the smallest number divisible by three different primes is 30 and n2 0 \leq52 = 25 < 30, it follows that n1 is of the form n1 = pr or n1 = pr \cdotqs, where p and q are two different primes. In the first case player B can choose 1 and win, while in the second case he can select the smaller of pr, qs, which is also smaller than \sqrtn1 \leqn0. Thus player B can eventually reach n2k = 1. Thus {2, 3, 4, 5} \subseteqL. Finally, for n0 = 6 or n0 = 7 player A must select a number divisible by at least three primes, which must be 30 = 2 \cdot 3 \cdot 5 or 42 = 2 \cdot 3 \cdot 7; otherwise, B can select a degree of a prime smaller than n0, yielding n2 < 6 and victory for B. Player B must select a number smaller than 8. Hence, he has to select 6 in both cases. Afterwards, to avoid losing the game, player A will always choose 30 and player B always 6. In this case we would have a tie. Hence T \subseteq{6, 7}. Considering that we have accounted for all integers n0 > 1, the final solution is L = {2, 3, 4, 5}, T = {6, 7}, and W = {x \inN | x \geq8}.