Азия-тынық мұхит математикалық олимпиадасы, 2015 жыл

Егер $a_0,a_1,\ldots$ нақты сандар тізбегі үшін келесі шарттар орындалса, онда ондай тізбекті {\em жақсы} тізбек деп айтамыз:
(i) $a_0$ — натурал сан;
(ii) кез келген теріс емес бүтін $i$ үшін $a_{i+1}=2a_i+1$ немесе ${\displaystyle a_{i+1}=\dfrac{a_i}{a_i+2}}$ қатынастары орындалады;
(iii) $a_k=2014$ болатындай натурал $k$ саны табылады.
Жақсы $a_0,a_1,\ldots$ тізбегі бар болатындай және $a_n=2014$ теңдігі орындалатындай ең кіші натурал $n$ санын табыңыз. ( Wang Wei Hua )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Заметим, что $$a_{i+1} + 1=2(a_i+1) \text{ или } a_{i+1}+1=\frac{a_i+a_i+2}{a_i+2}=\frac{2(a_i+1)}{a_i+2}.$$ Следовательно, $$\frac{1}{{{a_{i + 1}} + 1}} = \frac{1}{2} \cdot \frac{1}{{{a_i} + 1}} \text{ или } \frac{1}{{{a_{i + 1}} + 1}} = \frac{{{a_i} + 2}}{{2({a_i} + 1)}} = \frac{1}{2} \cdot \frac{1}{{{a_i} + 1}} + \frac{1}{2}.$$ Поэтому, $$\frac{1}{{{a_{k}} + 1}} = \frac{1}{{{2^k}}} \cdot \frac{1}{{{a_0} + 1}} + \sum\limits_{i = 1}^k {\frac{{{\varepsilon _i}}}{{{2^{k - i + 1}}}}}, \quad \mbox{где } \varepsilon _ i=0 \mbox{ или } 1. \quad (1)$$
Умножая обе части на $2^k(a_k+1)$ и полагая $a_k=2014$, имеем: $${2^k} = \frac{{2015}}{{{a_0} + 1}} + 2015 \cdot \left( {\sum\limits_{i = 1}^k {{\varepsilon _i} \cdot {2^{i - 1}}} } \right),$$ где $\varepsilon _ i=0$ или 1. Поскольку $\text{НОД}(2,2015)=1$, находим: $a_0+1=2015$ и $a_0=2014$.
Следовательно, $${2^k} - 1 = 2015 \cdot \left( {\sum\limits_{i = 1}^k {{\varepsilon _i} \cdot {2^{i - 1}}} } \right),$$ где $\varepsilon _ i=0$ или 1. Теперь необходимо найти наименьшее $k$ с условием ${2015|2^k-1}$. Так как $2015=5 \cdot 13\cdot 31$, применяя малую теорему Ферма, получаем: ${5|2^4-1}$, ${13|2^{12}-1}$ и ${31|2^{30}-1}$. Также имеем: $\text{НОК}[4,12,30]=60$, поэтому ${5|2^{60}-1}$, ${13|2^{60}-1}$ и ${31|2^{60}-1}$, что приводит к ${2015|2^{60}-1}$. Но ${5\nmid2^{30}-1}$, значит, $k=60$ — наименьшее натуральное с условием ${2015|2^k-1}$. Итак, наименьшим натуральным $k$, для которого $a_k=2014$, является $k=60$.