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

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

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

Ответ: $f(n)=n,\forall n\in\mathbb N$

Допустим $f-$ ограниченная функция.

Пусть $\max f(x)=f(A)$, но тогда $$P(A,1):f(f(A)f(1)+A)=f(Af(1))+f(A)>f(A)$$

что противоречить предположению. Значит $f-$ неограниченная функция.

$\quad$

Заметим, что $f(f(m)f(n)+m)>f(mf(n))$, откуда $$f(m)f(n)+m>mf(n)\implies m>f(n)(m-f(m))$$ так как. $f-$ неубывающая функция.

$\quad$

Если $f(t)<t$, для некоторого $t\in\mathbb N$, то $$t>f(n)(t-f(t))\implies \frac{t}{t-f(t)}>f(n)$$

что невозможно, ведь $f-$ неограниченная функция.

Откуда $f(n)\ge n, \forall n\in\mathbb N$

$\quad$

Пусть $f(1)=c$. Тогда

$$P(m,1):f(m)c+m\le f(f(m)c+m)=f(mc)+f(m)$$ $$\iff$$ $$f(mc)\ge f(m)(c-1)+m\quad (1)$$

Так же отметим

$$P(1,m):f(cf(m))\le f(cf(m)+1)=f(f(m))+c\quad (2)$$

Из $(1)$ и $(2)$ получаем, что $$f(f(m))(c-1)+f(m)\le f(f(m))+c$$ $$\iff$$ $$f(f(m))(c-2)+f(m)\le c $$

Если $c\ge 2$, то $$f(m)\le f(f(m))(c-2)+f(m)\le c$$

откуда $f(m)\le c,\forall m\in\mathbb N$, что невозможно.

Значит $c=1$, тогда $$P(1,n): f(f(n)+1)=f(f(n))+1 \quad (\mathrm i)$$

Так как $f(1)=1$, то индукцией, пользуясь $(\mathrm i)$ легко доказать, что $$f(n)=n,\forall n\in\mathbb N$$