қазақша
русскийРеспубликанская олимпиада по математике, 2025 год, 10 класс
Комментарий/решение:
Решение. Перепишем условие как $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$
Заменим $m=n+1$ и получаем ключевое уравнение:
$$0<f(n+1)-f(n)=f((n+1)f(n))-f(nf(n+1))$$
Так как $f$ строго возрастающее то чтобы неравенство выполнялось верно следующее:
$$(n+1)f(n) \geq nf(n+1)+1$$
Ключевое неравенство:
$$f(n)-1 \geq n(f(n+1)-f(n))$$
Расмотрим пошаговые суммы $f(n+1)-f(n)$, так как они натуральные существует наименьшее натуральное значение $k=f(p+1)-f(p)$ для какого-то натурального $p$.
Утверждение 1: $f(p)=pk+1$ и $f(p+1)=(p+1)k+1$
Чтобы доказать вставляем в ключевое уравнение $n=p$:
$$k=f((p+1)f(p))-f(pf(p+1))$$
Что возможно тогда и только когда $(p+1)f(p)=pf(p+1)+1$, иначе правая часть выражения можно будет записать как сумма хотя бы 2 последовательных пошаговых сумм в форме: $$(f(k+1)-f(k))+(f(k+2)-f(k+1))+... \geq 2k$$
$$(p+1)f(p)=pf(p+1)+1=p(f(p)+k)+1$$
$$f(p)((p+1)-p)=f(p)=pk+1$$
$$f(p+1)=f(p)+k=(p+1)k+1$$
Утверждение 2: $f(n)=nk+1$ для $n \leq p$.
$$f(p)-f(n)=(f(p)-f(p-1))+...+(f(n+1)-f(n))=kp+1-f(n) \geq (p-n)k$$
$$kn+1 \geq f(n)$$
Ключевое неравенство:
$$f(n)-1 \geq n(f(n+1)-f(n)) \geq nk$$
$$f(n) \geq nk+1$$
Утверждение 3: Если $f(j)=jk+1$ для $j>p$ то $f(j+1)=(j+1)k+1$
Для базы $j=p+1$ уже было доказано. Докажем само утверждение используя ключевое неравенство.
$$jk=f(j)-1 \geq j(f(j+1)-f(j)) \geq jk$$
$$k \geq f(j+1)-f(j) \geq k$$
$$(j+1)k+1=k+jk+1 \geq f(j+1) \geq (j+1)k+1=k+jk+1$$
Совмещяя утверждения получаем $f(n)=nk+1$ для любого $n$ и какого-то $k$.
Вставив в изначальное уравнение убеждаемся что ответ подходит.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.