Азиатско-Тихоокеанская математическая олимпиада, 2015 год

Последовательность действительных чисел $a_0, a_1, \ldots$ будем называть хорошей, если выполняются следующие три условия.
(i) $a_0$ — натуральное число.
(ii) Для каждого целого неотрицательного $i$ выполнено хотя бы одно из равенств $a_{i+1}=2a_i+1$, $a_{i+1}=\dfrac{a_i}{a_i+2}$.
(iii) Существует натуральное $k$ такое, что $a_k=2014$.
Найдите наименьшее натуральное $n$ такое, что существует хорошая последовательность $a_0, a_1, \ldots$ действительных чисел, для которой $a_n=2014$. ( 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$.