Республиканская олимпиада по математике, 2025 год, 10 класс

Найдите все строго возрастающие функции $f:\mathbb N\to \mathbb N$ такие, что $f(mf(n))+f(n)=f(nf(m)) + f(m)$ при всех $m,n\in \mathbb N$. (Здесь $\mathbb N$ — множество натуральных чисел.) ( Абу А. )

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

Решение. Перепишем условие как $f(mf(n)) - f(nf(m)) = f(m) - f(n).$ Подставив $m = n+1$ получим $$f((n+1)f(n)) - f(nf(n+1)) = f(n+1) - f(n).$$

Пусть $d = \min\limits_{k\in\mathbb N} (f(k+1)-f(k))$ и $S = \{k \mid k\in\mathbb N, f(k+1) - f(k) = d\}$. Понятно, что $S$ непустое.

Лемма. Для натуральных $a \ge b$ имеем $f(a) - f(b) \ge d(a-b)$.

Доказательство. Так как $f(n+1)-f(n)\ge d$ при всех $n\in \mathbb N$, то

$$f(a) - f(b) = (f(a) - f(a-1)) + (f(a-1) - f(a-2)) + \ldots + (f(b + 1) - f(b)) \ge d(a-b).$$

В частности, если $f(a) - f(b) = d$, то $a - b = 1$. $\square$

Утверждение 1. $S$ --- бесконечно и $f(k) = dk + 1$ для любого $k \in S$.

Доказательство. Пусть $k \in S$, тогда $f((k+1)f(k)) - f(kf(k+1)) = d$. Это означает, что $kf(k+1) \in S$, причем $kf(k+1) \ge 2k > k$. Значит $S$ --- бесконечно. Из $(k+1)f(k) - kf(k+1) = 1$ и $f(k+1) = f(k) + d$ следует, что $f(k) = dk + 1$. $\square$

Утверждение 2. $S = \{M, M+1, M+2, \ldots\}$ для некоторого натурального $M$.

Доказательство. Обозначим через $M$ наименьший элемент $S$. Пусть $a > b$ лежат в $S$. Из утверждения 1 получаем, что $f(a) - f(b) = (da+1)-(db+1) = d(a-b)$, тогда неравенство в лемме превращается в равенство. Следовательно $b, b+1, \ldots, a\in S$. Последнее, вместе с тем, что $S$ --- бесконечно, завершает доказательство. $\square$

Рассмотрим произвольное число $m\in \mathbb N$. Подставим в изначальное равенство $n \ge M$. Тогда $mf(n)\ge M$ и $nf(m) \ge M$, следовательно

$$dmf(n) - dnf(m) = f(m) - f(n) \implies f(m)\cdot(dn + 1) = f(n)\cdot (dm + 1),$$

откуда $f(m) = dm + 1$.

Ещё решение без пределов:

$$f((n+1)f(n))+f(n)=f(nf(n+1))+f(n+1)$$

$$f((n+1)f(n))-f(nf(n+1))=f(n+1)-f(n)>0$$

Поскольку $f$ строго возрастает, $(n+1)f(n)>nf(n+1)$, $значит\frac{f(n)}{n} \geq \frac{f(n+1)}{n+1}$ и $\lfloor \frac{f(n)}{n} \rfloor \geq \lfloor \frac{f(n+1)}{n+1} \rfloor$.

Раз последовательность $\lfloor \frac{f(n)}{n} \rfloor$ состоит из натуральных чисел (потому что $f(n) \geq n$) и невозрастает, она с какого-то момента постоянна, т.е. есть такое натуральное $a$, что для достаточно больших $n$, $\lfloor \frac{f(n)}{n} \rfloor = a$

Теперь посмотрим на последовательность $f(n)-an$ для достаточно больших $n$ (таких, что $\lfloor \frac{f(n)}{n} \rfloor = a$ и $n \geq a$).

Пусть, $f(n)=an+b$, $0 \leq b < a$. С другой стороны, $f(n+1) < f(n)+\frac{f(n)}{n}=an+b+a+\frac{b}{n}=a(n+1)+\frac{b}{n}$. Поскольку $b<a\leq n$, число $\frac{b}{n}$ меньше $1$, значит $f(n+1)-a(n+1) \leq b$.

То есть, частное при деление $f(n)$ на $n$ с какого-то момента не изменяется, а остаток не увеличивается, значит с какого-то момента $f(n)$ линейна.

Дальше как и в других решениях подставляем большое $n$ и $m=n+1$ в изначальное уравнение, чтобы получить, что с какого-то момента $f(n)=an+1$, потом подставляем большое $n$ чтобы получить, что для любого $m$: $f(m)=am+1$. Ну и понятно, что все такие функции подходят

Интересно, что данное решение доказывает такой факт: Если $(a_n)_{n=1}^\infty$ последовательность натуральных чисел и $\frac{a_n}{n}$ не возрастает, то с какого-то момента $a_n$ линейна.

Во время решения этой задачи, казалось, что это слишком хорошо, чтобы быть правдой. Но с ним задача просто очевидна и к сожалению лишается всякой красоты

Легко можно убедиться что функция $\frac{f(n)}{n}$ - убывающая. Действительно, при $m>n$, $f(m)>f(n)$, соответственно, $f(mf(n))>f(nf(m))$, откуда $mf(n)>nf(m)$, а значит при $m>n$, $\frac{f(n)}{n}>\frac{f(m)}{m}$. Так как $f(n)>0$, по теореме Вейерштрасса получаем что у функции $\frac{f(n)}{n}$ имеется предел равный некой $c$

То есть $\mathop {\lim } \limits_{n \to \infty} \frac{f(n)}{n}= c$

Также поймем что $\frac{f(n)}{n+1}$ - возрастающая функция

$f(mf(n))-f(nf(m))=f(m)-f(n)$

Заметим, что $f(mf(n))-f(nf(m))\geq mf(n)-nf(m)$

Это верно просто из за серий следующих неравенств:

$f(mf(n))-f(mf(n) -1)\geq 1$

$f(mf(n)-1)-f(mf(n) -2)\geq 1$

...

$f(nf(m)+1)-f(nf(m))\geq 1$

Их кол-во $mf(n)-nf(m)$, соответственно то неравенство верное

Тогда давайте докажем что $\frac{f(n)}{n+1}$ также имеет предел

Это довольно легко : $\mathop {\lim } \limits_{n \to \infty} \frac{f(n)}{n+1} = \mathop {\lim } \limits_{n \to \infty} \frac{f(n)}{n} * \frac{n}{n+1} = c * 1 = c$

Тогда поймем что следующее неравенство верное:

$\frac{f(n)}{n} > f(n+1)-f(n)\geq \frac{f(n)}{n+1}$

Действительно, левое неравенство перепишется как:

$\frac{f(n)}{n}>\frac{f(n+1)}{n+1}$

Правое же неравенство перепишется как:

$\frac{f(n)}{n+1}\leq \frac{f(n+1)}{n+2}$

Тогда по теореме о двух милиционерах поймем что и у $\frac{f(n)}{n}$ и у $\frac{f(n)}{n+1}$ есть предел равный $c$. Значит

$\mathop {\lim } \limits_{n \to \infty} f(n+1)-f(n)= c$

Но заметим что так как $f(n+1)-f(n) \in \mathbb{Z}$, то во первых $c$ - целое иначе если расстояние от $c$ до ближайшего целого равно некой константе $d$, то $f(n+1)-f(n)$ никогда не сможет приблизиться к $c$ меньше чем на $d$, а это противоречит существованию предела

Во вторых, с какого то момента $\forall n \geq t$, выполнено следующее:

$f(n+1)-f(n)=c$, иначе если этого момента никогда не будет то всегда для бесконечно многих $n$, $f(n+1)-f(n)$ будет минимум на расстоянии $1$ от $c$, что противоречит существованию предела

Тогда действительно $\forall n \geq t, f(n+1)-f(n)=c$

Это значит что $\forall n \geq t, f(n)=f(t)+c(n-t)$

Тогда давайте рассмотрим подстановку $P(t, t+1)$

Сразу понятно что $tf(t+1), (t+1)f(t) \geq t$ это вполне очевидно

$f(tf(t+1))+f(t+1)=f((t+1)f(t))+f(t)$

$f(t)+c(tf(t+1)-t)+f(t+1)=f(t)+c((t+1)f(t)-t)+f(t)$

$ctf(t+1)-ct+f(t+1)=ctf(t)+cf(t)-ct+f(t)$

$ctf(t)+c^2t+f(t)+c=ctf(t)+cf(t)+f(t)$

$c^2t+c=cf(t)$

$f(t)=ct+1$

Откуда и следует что $\forall n \geq t, f(n)=cn+1$

Тогда $P(m, n)$, где $m<t, n>t$

$f(m)n, nf(m) > t$

$f(mf(n))+f(n)=f(nf(m))+f(m)$

$cmf(n)+1+f(n)=cnf(m)+1+f(m)$

$c^2mn+cm+1+cn=(cn+1)f(m)$

$(cn+1)(cm+1)=(cn+1)f(m)$

$f(m)=cm+1$

Причем важно что $c \in \mathbb{Z}$, $c>0$, так как $\mathop {\lim } \limits_{n \to \infty} \frac{f(n)}{n}= c$, откуда так как $f$ - возрастающая то $f(n)\geq n \longrightarrow c\geq 1$