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


Пусть $\mathbf{N}$ — множество всех натуральных чисел. Определите все функции $f: \mathbf{N} \to \mathbf{N}$ такие, что для любых натуральных чисел $m,~n$ выполнены неравенства $2f(mn) \ge f(m^2 + n^2) - f(m)^2 - f(n)^2 \ge 2f(m)f(n).$ ( Сатылханов К. )
посмотреть в олимпиаде

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

Комментарии от администратора Комментарии от администратора №1.     Решение. Пусть $A = \{k\ |\ f(kn) = k^2f(n)\ \forall n \in \mathbf{N} \}$ и $A_1 = \{k\ |\ f(k) = k^2 \}$. По условию имеем следующие неравенства: \begin{align*} f(mn) \ge f(m)f(n), &\quad (1) \\ f(m^2 + n^2) \ge (f(m) + f(n))^2, &\quad (2) \\ f(m)^2 + f(n)^2 + 2f(mn) \ge f(m^2 + n^2). &\quad (3) \\ \end{align*}
Лемма 1. Если $f(mn) = f(m)f(n),$ то $f(m^2 + n^2) = (f(m) + f(n))^2$.
Доказательство. Легко следует из неравенств$~(1),~(2)$. $\square$
При $m = n = 1$ из$~(1)$ $f(1) \ge f(1)^2$, откуда $f(1) = 1.$ Положив $m = 1$ выполнено $f(mn) = f(m)f(n),$ тогда по Лемме 1 имеем $$ f(n^2 + 1) = (f(n) + 1)^2\ \forall n \in \mathbf{N}. \quad (4) $$ Из$~(4)$ при $n = 1,$ $f(2) = 4.$ Из$~(3),~(1)$ при $m = n$ имеем $$ 2f(n)^2 + 2f(n^2) \ge f(2n^2) \ge f(2) f(n^2) = 4 f(n^2) \implies f(n)^3 \ge f(n^2), $$ и при $m = n$ из$~(1)$ имеем $f(n^2) \ge f(n)^2.$ Следовательно, $$ f(n^2) = f(n)^2\ \forall n \in \mathbf{N}. \quad (5) $$
Лемма 2. Если $f(kn^2) = k^2f(n)^2 = k^2 f(n^2)\ \forall n \in \mathbf{N},$ то $k \in A.$
Доказательство. $f(k) = f(k \cdot 1^2) = k^2 f(1)^2 = k^2$, $k^2 f(n)^2 = f(k n^2) \ge f(kn) f(n) \implies f(kn) \le k^2f(n)$ и $f(kn) \ge f(k)(n) = k^2 f(n) \implies f(kn) = k^2 f(n) \implies k \in A.$ $\square$
Так как при $m = n$ верно $f(mn) = f(m)f(n)$, по Лемме 1 $f(2n^2) = 4 f(n)^2$. Тогда, по Лемме 2 $$ f(2n) = 4f(n)\ \forall n \in \mathbf{N}. \quad (6) $$ Следовательно, $2 \in A$. Из$~(1)$ если $n = p_1 \cdots p_k,$ то $$ f(n) \ge f(p_1) \cdots f(p_k). \quad (7) $$ Докажем теперь индукцией по $n$, что $$ f(n) \ge n^2\ \forall n \in \mathbf{N}. \quad (8) $$ При $n = 1,2,$ $f(n) = n^2.$ Предположим$~(8)$ верно при всех $k < n.$ Докажем для $n \ge 3.$

  1. Если $n$ составное, то $n = mk$ для $1 < m,k < n.$ Тогда из$~(1)$ $f(n) \ge f(m)f(k) \ge m^2 k^2 = n^2.$
  2. Если $n$ простое виде $4k + 1$. По теореме Ферма найдутся $x,y\in \mathbf{N}$ такие, что $n = x^2 + y^2$. Тогда из$~(2)$ $f(n) = f(x^2 + y^2) \ge (f(x) + f(y))^2 \ge (x^2 + y^2)^2 = n^2.$
  3. Если же $n$ простое вида $4k + 3$, то $n^2 + 1 = 2 p_1 \cdots p_k,$ для простых $p_i = 4k_i + 1$, $i = 1, \ldots, k$. Тогда найдутся $x_i, y_i \in \mathbf{N}$ такие, что $x_i^2 + y_i^2 = p_i \le \frac{n^2 + 1}{2} < n^2 \implies x_i, y_i < n \implies$ $f(p_i) \ge f(x_i^2 + y_i^2) \ge (f(x_i) + f(y_i))^2 \ge (x_i^2 + y_i^2)^2 = p_i^2$. Из$~(7)$ $\implies f(n^2 + 1) \ge f(2) f(p_1) \cdots f(p_k) \ge 2^2 p_1^2 \cdots p_k^2 = (n^2 + 1)^2$, из$~(4)$ $\implies f(n) = \sqrt{f(n^2 + 1)} -1 \ge n^2.$ $\square$
Лемма 3. Если $a,b \in A,$ то $ab \in A$ и $a^2 + b^2 \in A$.
Доказательство. $f(an) = a^2 f(n)\ \forall n \in \mathbf{N}$ и $f(bn) = b^2 f(n)\ \forall n \in \mathbf{N}$. Тогда $f(abn) = a^2 f(bn) = a^2b^2f(n) \implies ab \in A.$ При $x = an, y = bn$ $f(xy) = f(abn^2) = (ab)^2f(n)^2 = (a^2f(n))(b^2f(n)) = f(an)f(bn) = f(x)f(y)$. По Лемме 1 $f((a^2 + b^2)n^2) = f(x^2 + y^2) = (f(x) + f(y))^2 = (a^2 + b^2)^2 f(n)^2$, откуда по Лемме 2 $a^2 + b^2 \in A.$ $\square$
Лемма 4. Если $k \in A$ и $d$ является делителем $k$, то $d \in A$.
Доказательство. Из$~(8)$ имеем $k^2 f(n) = f(kn) \ge f(dn) f(k/d) \ge (k/d)^2 f(dn) \implies d^2 f(n) \ge f(dn) \ge f(d) f(n) \ge d^2 f(n) \implies f(dn) = d^2 f(n) \implies d \in A.$ $\square$
Построим бесконечную последовательность $\{p_i \}$ различных простых чисел такую, что $p_1 = 2$ и $\forall k$ $p_{k+1}$ -- простой делитель числа $(p_1 \cdots p_k)^2 + 1$. Тогда $p_i \equiv 1 \pmod{4}.$ Докажем индукцией по $k$, что $$ p_k \in A. \quad (9) $$ Для $k = 1$ это верно. По Лемме 3, так как $p_i \in A$ для $i = 1, \ldots, k$ и $1 \in A,$ то $p_1 \cdots p_k \in A$ и $x = (p_1 \cdots p_k)^2 + 1 \in A$, откуда по Лемме 4 $p_{k+1} \in A.$ $\square$
Лемма 5. $r = a^2 + b^2 \in A_1 \implies a,b \in A_1$.
Доказательство. $r \in A_1 \implies f(r) = r^2$. Из$~(2),~(8)$ $r^2 = f(r) = f(a^2 + b^2) \ge (f(a) + f(b))^2 \ge (a^2 + b^2)^2 = r^2 \implies f(a) = a^2, f(b) = b^2, \implies a,b \in A_1.$ $\square$
Лемма 6. Если $r \in A_1$ и $d$ является делителем $r$, то $d \in A_1$.
Доказательство. $r = kd \implies d^2 \le f(d) \le f(r)/f(k) = r^2/f(k) \le r^2/k^2 = d^2 \implies f(d) = d^2.$ $\square$
Из$~(9)$ $\forall i$ $f(p_i) = p_i^2$, $p_1 = 2 = 1^2 + 1^2$ и при $i \ge 2, p_i \equiv 1 \pmod{4}$, то $\forall i$ найдутся $x_i, y_i \in \mathbf{N}$ такие, что $p_i = x_i^2 + y_i^2$. Рассмотрим произвольное $n \in \mathbf{N}$ и числа $(y_i, n)$ (НОД). Среди них какое-то число встречается бесконечно много раз, пусть это $d$. Рассмотрим бесконечное множество $B = \{ i\ |\ i \in \mathbf{N}, (y_i, n ) = d\}$ и $y_i = dz_i$ $\forall i \in B, (z_i, n) = 1.$ Тогда существуют $i < j$ ($i,j \in B$) такие, что $x_i/z_i \equiv x_j/z_j \pmod{n} \implies $ $s = |x_iy_j - x_jy_i| = |d(x_iz_j - x_jz_i)|$ делится на $n$ и $t = x_i x_j + y_iy_j$ $\implies p_i p_j = s^2 + t^2 \implies s > 0.$ Так как $p_i, p_j \in A$ по Лемме 3 $p_ip_j \in A \implies f(p_ip_j) = (p_ip_j)^2 \implies p_ip_j \in A_1$. По Лемме 5 $s,t \in A_1$ и так как $s$ делистя на $n$, то по Лемме 6 $n \in A_1 \implies f(n) = n^2 \forall n \in \mathbf{N}.$ Легко видеть, что ответ удовлетворяет начальным условиям.

пред. Правка 2   6
2022-08-16 01:26:59.0 #

Пусть $P(m,n)$ условие.

Claim 1: $f(n^2+1)\equiv(f(n)+1)^2$ и $f(1)=1, f(2)=4.$

Это следует из $P(n,1).$

Claim 2: $f(n^2)\equiv f(n)^2\implies f(2n)\equiv 4f(n)$

Первое равенство просто следует из $P(n,n).$ Отсюда же легко вывести, что $f(2n^2)=4f(n^2).$ Подставив это в $P(2n,n)$ получаем, что $f(2n)\equiv 4f(n).$

$\bullet$ Далее индукцией докажем, что $f(k)\equiv k^2.$

Допустим, что $f(i)=i^2, 1\le i \le k-1,$ где $k\ge 3.$

(i) Если $2\mid k,$ то $f(k)=4f(\frac{k}{2})=k^2.$

(ii) Пусть теперь $k=2x+1.$ Далее заметим, что

$$(f(2x+1)+1)^2=f(4x^2+4x+2)=4f(2x^2+2x+1)$$

Из $P(x,x+1): f(x^2+(x+1)^2)-f(x)^2-f(x+1)^2\ge 2f(x)f(x+1),$ причем мы знаем, что $f(x)=x^2,f(x+1)=(x+1)^2$

$$\implies f(2x^2+2x+1)\ge (2x^2+2x+1)^2\implies \boxed{f(2x+1)\ge (2x+1)^2}$$

Из $P(2x+1,2x-1): (f(2x+1)+(2x-1)^2)^2 \le f((2x+1)^2+(2x-1)^2)=4f((2x)^2+1)=4(f(2x)+1)^2=4((2x)^2+1)^2$

$$\implies \boxed{f(2x+1)\le (2x+1)^2}$$

Переход доказан. Значит $\boxed {f(n)\equiv n^2},$ что подходит под изначальное условие.

ASDF