58-я Международная Математическая OлимпиадаБразилия, Рио-де-Жанейро, 2017 год

Әрбір $a_0 > 1$ бүтін саны үшін, $a_0$, $a_1$, $a_2$, $\ldots$ тізбегін осылай анықтайық: $${a_{n + 1}} = \left\{ \begin{array}{l} \sqrt {{a_n}} ,\mbox { егер } {\sqrt{a_n}} \mbox { — бүтін болса},\\ {a_n} + 3 \mbox { кері жағдайда,} \end{array} \right. \mbox { барлық } n \ge 0 \mbox { үшін}. $$ Келесі шарт орындалатындай $a_0$ барлық мәндерін табыңыз: шексіз көп $n$ сандары үшін $a_n=A$ болатын $A$ саны бар.

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

"Набросок решения"

Если $3\mid a_0,$ то докажите, что $a_i\le (3t)^2,\forall i\in\mathbb N,$ где $t\in\mathbb N,a_0\le {(3t)}^.2$ $\quad (t$ константа)

Если $2\equiv a_i\pmod 3,$ для некоторого $i\in\mathbb N_0,$ то ни один член последовательности не является целым квадратом, поскольку $x^2\equiv \{0,1\} \pmod 3.$

Если $1\equiv a_i\pmod 3,$ для всех $i\in\mathbb N_0,$ то для каждого $j\in\mathbb N_0,$ существует $k_j\in\mathbb N_0,$ что $$a_j> a_{k_j}\quad \text{и}\quad k_j> j.$$ Тогда для некоторого $\ell\in\mathbb N_0,a_{\ell}=1,$ но тогда $a_i\ge a_{\ell}=1,$ что противоречит свойству доказанному ранее.

Свойство легко доказать, если ограничить $s^2 < a_j\le (s+1)^2,s\in\mathbb{N_0},$ а далее рассмотрев случаи $s\equiv \{0,1,2\}\pmod 3.$

Если $a_i \equiv 2 \pmod {3}$ то заметим что все последующие числа тоже будут давать такой же остаток откуда заметим что это будет возрастающая последовательность тогда таких $a_0$ нету

Пусть теперь же $a_i\equiv 1 \pmod {3}$ если $a_i\ne 1$ тогда если $\sqrt{a_i} \in Z \Rightarrow a_{i-1}\equiv 2 \pmod {3} \Rightarrow $ и так бесконечно вниз и это будет возрастающей последовательности а если $\sqrt {a_i}$ не целое то если после $t$ действий опять не будет целое то это будет опять же возрастающей последовательности и такового $A$ не будет тогда если $a_i=1 \Rightarrow a_i=a_{i-1}=....=a_0=1 \Rightarrow A=1$

$a_i \equiv0\pmod {3}$ Тогда все числа в этой последовательнсоти $\equiv 0 \pmod {3}$

Допустим теперь $a_i$ квадрат какого то числа После $p$ дествий мы дойдем до того что $a_u=a_i$ и тогда это будет бесконечная последовательность

Докво если $a_i$ квадрат то после первого действия он уменьшится но т.к. последующий числа будут возрастать то он опять же вырастет тогда Если $a_i$ не квадрат то он возрастет до квадрата какого то числа и опять спустится и если следующее число не квадрат то бесконечная последовательность и если это число еще какого квадрата и т.д. несколько раз то это будет опять бесконечная последовательность или они достигнут предела в $\sqrt{9}=3,3+3=6,6+3=9$ и это бесконечная последовательнсоть откуда

$a_0=3s,1$

Правильно ?просто это второй раз когда последовательность решаю

Можно переформулировать вопрос так: Нужно найти все такие числа, которые в результате данных действий, не попадут в цикл. Не для кого не секрет, что квадрат целого числа никогда не даст 2 в остатке при делении на 3.

Расмотрим возможные попадания в числа {1,2,3,4,5}. Если изначально число не кратно 3, то оно никогда кратным 3 не станет, так как корень не умножить на 3, а прибавление 3 ее остаток оставит. Если это число 2,5 - то выходит что мы будем добавлять бесконечно 3, и остаток всегда 2 => в цикл не попали

Если 1,4 - то из 1 мы перейдем в 4, а из 4 в 2=> не попали в цикл. Значит если число кратно 3, то ее кратность не уйдет, так как корень 3 не уберет, а +3 не добавит остаток. И так, если мы попали в 3, то выйдет что 3=>6=>9=>3…. - попали в цикл. А доказать что число всегда попадает в {1,2,3,4,5} хоть раз, можно получить с помощью неравенства. Допустим мы дошли до такого х, что (а-1)^2<х<=а^2 = > х<=5( можно догодатся, что х<=а+2, так как а, а+1, а+2 - дают всевозможные остатки от 3=>х<=5). Тогда ответ:

Попадаем в цикл если число кратно 3

Не попадаем если число не кратно 3

Сначала глянем на остатки по модулю $3$. Квадрат всегда даёт $0$ или $1 \pmod 3$, а прибавление $3$ остаток не меняет. Значит, важно, в каком классе по модулю $3$ мы стартуем.

1) $a_0\equiv0\pmod3$.

Тогда у нас всегда числа $3,6,9,12,\dots$. Когда-то дойдём до квадрата $9t^2$, возьмём корень $3t$, и снова всё повторится. Тут всё хорошо, такие $a_0$ работают.

2) $a_0\equiv2\pmod3$.

Тут сразу беда: квадрат никогда не бывает вида $3k+2$. Значит, сколько бы мы ни прибавляли тройку, квадрат не встретится. Последовательность просто улетает вверх. Такие $a_0$ не подходят.

3) $a_0\equiv1\pmod3$.

Вот тут поинтереснее. Рано или поздно дойдём до квадрата $(3t+1)^2$, потом возьмём корень $3t+1$ и опять получим число вида $3k+1$, только меньше. Повторяя этот процесс, в итоге свалимся в маленькие числа (по типу до тех пор, пока $3k+3t+1=(3k+1)^2$ и $3k+1 > (3k-1)^2$, а отсюда $k<9$). Давайте их проверим руками:

$$7\to10\to13\to16\to4\to2,\qquad 10\to13\to16\to4\to2,\qquad 13\to16\to4\to2.$$

А ещё $4\to2$. Дальше цикл идёт по малым числам. Значит, именно $4,7,10,13$ годятся.

---

Итого у нас остаются:

$$\boxed{3k,\;4,\;7,\;10,\;13}.$$