XV математическая олимпиада «Шелковый путь», 2016 год

Даны натуральные числа $a,b$ и функция $f: \mathbb{N} \to \mathbb{N} $ такая, что для любого натурального $n$ число $f\left( n+a \right)$ делится на $f\left( {\left[ {\sqrt n } \right] + b} \right)$. Докажите, что для любого натурального $n$ существует $n$ попарно различных и попарно взаимно простых натуральных чисел ${{a}_{1}}$, ${{a}_{2}}$, $\ldots$, ${{a}_{n}}$ такие, что число $f\left( {{a}_{i+1}} \right)$ делится на $f\left( {{a}_{i}} \right)$ для каждого $i=1,2, \dots ,n-1$. (Здесь $[x]$ — целая часть числа $x$, то есть наибольшее целое число, не превосходящее $x$; $\mathbb{N}$ — множество натуральных чисел.) ( Сатылханов К. )

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

Построим строго возрастающую последовательность натуральных чисел $(a_i)_{i\ge 1}$, такую, что

$1)\quad (a_{n},\prod\limits_{i=1}^{n-1} a_i)=1,\forall n\in\mathbb N_{>1}$

$2)\quad f(a_{n-1})\mid f(a_n),\forall n\in\mathbb N_{>1}$

$\\$

Сперва докажем, что существует $a_1$ и $a_2$ удовлетворяющие заданым условиям.

Пуст $a_1=2b$ и $a_2=(b^2+s)+a$, для некоторого $1\le s\le 2b$, такого, что $(2b,b^2+s+a)=1$. $($Очевидно, что $a_2>a_2)$

$($такое $s$ существует, ведь можно принять, что $s\equiv 1-b^2-a\pmod {2b})$

Из условия задачи следует, что $$f(a_1)=f(b+b)=f([\sqrt{b^2+s}]+b)\mid f(b^2+s+a)=f(a_2)$$

$\\$

$\\$

Далее по индукцией, будем строить $a_{m+1}$, допуская, что условия $1)$ и $2)$ выполнены для $n$, от $2$ до $m$, где $m\ge 2$.

Пусть $A=\prod\limits_{i=1}^{m}a_i$. Заметим, что $a_m\ge a_1 +1= 2b+1$. Докажем, что существует $B>A$, такое, что $f(a_m)\mid f(B+b)$

$\\$

$\\$

Утверждение: Для любого $g\ge 2b+1$, существует бесконечно много натуральных $x$, такое, что $f(g)\mid f(x)$

Доказательство: Заметим, что для любого $n\ge 2b+1$ верно:

$(1)$ $\left\{\begin{gathered} f(n)=f((n-b)+b)\mid f((n-b)^2+a),\\ (n-b)^2+a\ge (n-b)^2+1\ge 2(n-b)\ge n+1,\\ \end{gathered}\right.$

Пусть $g_1=(g-b)^2+a$ и $g_{i+1}=(g_i-b)^2+a,\forall i\in\mathbb N$

тогда из $(1)\implies$ $f(g)\mid f(g_1),$ $f(g_i)\mid f(g_{i+1}),g_i<g_{i+1}, \forall i\in\mathbb N.\quad \square$

$\\$

$\\$

Значит $f(a_m)\mid f(B+b)$, для некоторого $B>A$.

Из условия : $f(B+b)\mid f(B^2+k+a)$, где $1\le k\le 2A$.

Тогда существует $k$, такое, что $(B^2+k+a,A)=1$

$($так как можно выбрать $k$, так, что бы $k\equiv 1-B^2-a\pmod A)$

Тогда пусть $a_{m+1}=B^2+k+a>A^2\ge A\ge a_m\implies a_{m+1}>a_m$.

Так же верно, что $f(a_m)\mid f(a_{m+1})$ и $(a_{m+1},A)=1.\quad \square$