1990 IMO Problems/Problem 5

Problem

Given an initial integer $n_{0}\textgreater1$, two players, $\mathbb{A}$ and $\mathbb{B}$, choose integers $n_{1}, n_{2},n_{3}$, . . . alternately according to the following rules: Knowing $n_{2k}$, $\mathbb{A}$ chooses any integer $n_{2k+1}$ such that \[n_{2k}\leq n_{2k+1}\leq n_{2k}^2\]. Knowing $n_{2k+1}$, $\mathbb{B}$ chooses any integer $n_{2k+2}$ such that \[\frac{n_{2k+1}}{n_{2k+2}}\] is a prime raised to a positive integer power. Player $\mathbb{A}$ wins the game by choosing the number 1990; player $\mathbb{B}$ wins by choosing the number 1. For which $n_{0}$ does:

(a) $\mathbb{A}$ have a winning strategy?

(b) $\mathbb{B}$ have a winning strategy?

(c) Neither player have a winning strategy?

Solution

If $n_0<6$ it is clear that B wins, because A can only choose numbers with at most 2 prime factors (30 is the smallest with three and $30>5^2$), which B can either make smaller (choose the lesser of the two) or the number contains one prime factor in which case B wins. Once $n_{2k}=2$, A can only choose prime powers, so B wins.

If $n_0=6,7$ it's a draw, because the only numbers that give A a chance of winning are those with three prime factors (for reasons discussed above). Less than 49, this gives 30 and 42 as the only choices which won't cause A to lose. However, if A chooses 30, B may choose 6, and we have a stalemate. If A chooses 42, B may choose 6, and we still have a stalemate.

If $n_0 \geq 8$, if $n_0$ is less than 45 by choosing (perhaps starting later) 3*4*5, then 3*5*7, then 2*3*5*7, and then 3*4*5*7 A can force B to make $n_{2k} \geq 60$ for some k.

If $45 \leq n_{2k} \leq 1990$ for some k, then A wins (he may pick 1990). If $n_{2k}>1990$ pick the least natural value of m such that $2^m 47\geq n_{2k}$. The best B can do is half it, taking it to $n_{2k+2} = 2^{m-1} 47 < n_{2k}$. However, B cannot make $n_{2k+2}$ drop below 45 because $47*32<1990 \Rightarrow 2^m \geq 64$. Thus we will get a descending sequence of integers until we end up with $45 \leq n_{2k} \leq 1990$, at which point A wins.

This solution was posted and copyrighted by Ilthigore. The original thread for this problem can be found here: [1]

See Also

1990 IMO (Problems) • Resources
Preceded by
Problem 4
1 2 3 4 5 6 Followed by
Problem 6
All IMO Problems and Solutions