Решения: Дистанционные олимпиады, Математическая олимпиада «Шелковый путь»

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.$

Если $n$ составное, то $n = mk$ для $1 < m,k < n.$ Тогда из $~(1)$ $f(n) \ge f(m)f(k) \ge m^2 k^2 = n^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.$
Если же $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}.$ Легко видеть, что ответ удовлетворяет начальным условиям.

ASDF

пред. Правка 2

2 года 8 месяца назад #

Пусть $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