Given an initial integer $ n_0 > 1$, two players, $ {\mathcal A}$ and $ {\mathcal B}$, choose integers $ n_1$, $ n_2$, $ n_3$, $ \ldots$ alternately according to the following rules : I.) Knowing $ n_{2k}$, $ {\mathcal A}$ chooses any integer $ n_{2k + 1}$ such that \[ n_{2k} \leq n_{2k + 1} \leq n_{2k}^2. \] II.) Knowing $ n_{2k + 1}$, $ {\mathcal 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 $ {\mathcal A}$ wins the game by choosing the number 1990; player $ {\mathcal B}$ wins by choosing the number 1. For which $ n_0$ does : a.) $ {\mathcal A}$ have a winning strategy? b.) $ {\mathcal B}$ have a winning strategy? c.) Neither player have a winning strategy?
Problem
Source: IMO 1990, Day 2, Problem 5, IMO ShortList 1990, Problem 6 (FRG 2)
Tags: combinatorics, game, game strategy, algorithm, IMO, IMO 1990
21.04.2008 18:43
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.
21.04.2008 19:58
It was problem 5 in the 1990 IMO in Beijing. I messed up the 6-7 case, otherwise I would have brought home a bronze...
18.06.2011 19:55
orl wrote: II.) Knowing $ n_{2k + 1}$, $ {\mathcal 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. Did I understand sth wrong if I think when $A$ choose $30$ or $42$, B can make it $2$? Because it makes the whole question in a different way than the solution I think to read??