Ukrainian Mathematical Olympiad

Question

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 a_n+1 3a_n for 1 n 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?

Accepted Answer

Андрійко може забезпечити собі перемогу. Для доведення досить показати, що Андрійко зможе записати число

a_{2006} = M - 1

, де

M = \sum_{k = 1}^{2005} a_{k}

. Очевидно, що

M - 1 \geq a_{2005}

. Доведемо, що Андрійко може забезпечити й виконання нерівності

a_{2006} = M - 1 \leq 3 a_{2005}

. Нехай Миколка своїм черговим ходом записує число

a_{2 k - 1}

, тоді Андрійко відповідає записом числа

a_{2 k} = 3 a_{2 k - 1}

,

1 \leq k \leq 1002

. Оскільки

a_{2 k + 1} \geq a_{2 k} = 3 a_{2 k - 1}

, то, додавши нерівності

a_{3} \geq 3 a_{1}

,

a_{5} \geq 3 a_{3}

, ...,

a_{2005} \geq 3 a_{2003}

, будемо мати, що

a_{2005} \geq 1 + 2 A

, де

A = a_{1} + a_{3} + ... + a_{2003}

. Таким чином,

M = a_{1} + 3 a_{1} + a_{3} + 3 a_{3} + \dots + a_{2003} + 3 a_{2003} + a_{2005} = = 4 A + a_{2005} \leq 2 (a_{2005} - 1) + a_{2005} = 3 a_{2005} - 2 < 3 a_{2005} .