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

Пусть $m$ фиксированное натуральное число. Бесконечная последовательность $\{a_n \}_{n \ge 1}$ определена следующим образом: $a_1$ — натуральное число и для всех $n \ge 1$ имеем $$ a_{n+1} = \begin{cases} a_n^2 + 2^m & \text{ если } a_n < 2^m\\ a_n/2 & \text{ если } a_n \ge 2^m. \end{cases} $$ Для каждого $m$, определите всевозможные значения $a_1$ такие, что каждый член последовательности является целым числом.

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

Заметим, что $\exists \, n, a_{n}<2^m$. Тогда определение возможных пар $(a_{1}, m)$ равнозначно нахождения всевозможных пар $(a_{i}, m), a_{i} < 2^m$ такие, что в последовательности $\{a_{n} \}$ все члены целые. Очевидно, что пара $(2,2)$ удовлетворяет условию задачи.

Пусть $a_{i} < 2^m$. Тогда рассмотрим последовательность $\{ b_{j} \}$, где $b_{k-i+1}$ наибольший нечетный делитель $a_{k}$. Заметим, что эта последовательность монотонно возрастающая. Это в самом деле так, так как операция деления на $2$ не уменьшает $b_{j}$, а если $b_{k}=p, a_{k+i-1}=2^sp \Rightarrow a_{k+i} = 2^{2s}p^2+2^m \Rightarrow b_{k+1} \in \{2^{2s-m}p^2+1, p^2+2^{m-2s}\} \Rightarrow b_{k+1} > b_{k}$. Тут мы использовали тот факт, что $a_{n}^2+2^m$ не степень двойки, что верно только для $m=2$. Значит $\exists \, k, b_{k} > 2^m \Rightarrow \exists \, n, a_{n} \notin \mathbb{N}$.

То есть единственная пара это $(2,2)$. А это означает, что так как были использована только операция деления попалам, то $a_{1}=2^k, \forall k \geq 1, m = 2$.