Track / Stage 7 / 38 of 300 #1918 of 2444

Problem 1918

National Olympiad second round; IMO P1/P4

Combinatorics Difficulty 7.0 Prove it Ukrainian Mathematical Olympiad · Ukraine

Mykolka and Andriyko are playing the following game. They write positive integers turn by turn thus forming a sequence $a_1, a_2, ..., a_{2006}$ obeying the following restrictions: $a_1 = 1$ (this first turn is fixed, and it is made by Mykolka), and $a_n \le a_{n+1} \le 3a_n$ for $1 \le n \le 2005$ . If, after the last turn was made, the sums $a_1 + a_2 + ... + a_{2004} + a_{2005}$ and $a_1 + a_2 + ... + a_{2005} + a_{2006}$ appear to be mutually prime numbers, then the winner is Andriyko, otherwise it is Mykolka. Who of the players can secure his victory whatever way the other one plays?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Андрійко може забезпечити собі перемогу. Для доведення досить показати, що Андрійко зможе записати число $a_{2006} = M - 1$ , де $M = \sum_{k=1}^{2005} a_k$ . Очевидно, що $M - 1 \ge a_{2005}$ . Доведемо, що Андрійко може забезпечити й виконання нерівності $a_{2006} = M - 1 \le 3a_{2005}$ . Нехай Миколка своїм черговим ходом записує число $a_{2k-1}$ , тоді Андрійко відповідає записом числа $a_{2k} = 3a_{2k-1}$ , $1 \le k \le 1002$ . Оскільки $a_{2k+1} \ge a_{2k} = 3a_{2k-1}$ , то, додавши нерівності $a_3 \ge 3a_1$ , $a_5 \ge 3a_3$ , ..., $a_{2005} \ge 3a_{2003}$ , будемо мати, що $a_{2005} \ge 1 + 2A$ , де $A = a_1 + a_3 + ... + a_{2003}$ . Таким чином,

$\begin{aligned} M &= a_1 + 3a_1 + a_3 + 3a_3 + \dots + a_{2003} + 3a_{2003} + a_{2005} = \\ &= 4A + a_{2005} \le 2(a_{2005} - 1) + a_{2005} = 3a_{2005} - 2 < 3a_{2005}. \end{aligned}$

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.