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]

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

Page

Toolbox

Search

1990 IMO Problems/Problem 5

Problem

Solution

See Also