Математикадан 37-ші халықаралық олимпиада, 1996 жыл, Мумбаи

$S=\left\{ 0,1,2,3,\ldots \right\}$ — теріс емес бүтін сандар жиыны болсын. $\forall\ m,n\in S$ үшін $f\left( m\text{ }+\text{ }f\left( n \right) \right)\text{ }=\text{ }f\left( f\left( m \right) \right)\text{ }+\text{ }f\left( n \right)$ орындалатындай $S$ жиынында анықталған барлық $f$ функцияларды табыңыздар.

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

Дефолт

\textbf{Задача.} Пусть $S = \{0,1,2,3,\dots\}$ — множество неотрицательных целых чисел. Найти все функции $f: S \to S$, такие что

\[

f(m + f(n)) = f(f(m)) + f(n) \quad \forall m,n \in S.

\]

\textbf{Решение.}

\textbf{Шаг 1. Подстановка $m = 0$}

Подставим $m = 0$ в исходное уравнение:

\[

f(0 + f(n)) = f(f(0)) + f(n) \implies f(f(n)) = f(f(0)) + f(n). \tag{1}

\]

---

\textbf{Шаг 2. Предположим линейную форму}

Так как уравнение похоже на линейное, рассмотрим

\[

f(n) = a n + b, \quad a,b \in \mathbb{Z}_{\ge 0}.

\]

Тогда:

\[

\begin{aligned}

f(m + f(n)) &= a(m + a n + b) + b = a m + a^2 n + a b + b, \\

f(f(m)) + f(n) &= f(a m + b) + (a n + b) = a^2 m + a b + b + a n + b = a^2 m + a n + a b + 2b.

\end{aligned}

\]

Сравнивая коэффициенты при $m$, $n$ и свободный член, получаем:

1. При $m$: $a = a^2 \implies a = 0 \text{ или } 1$.

2. При $n$: $a^2 = a \implies a = 0 \text{ или } 1$ — согласуется.

3. При свободном члене: $a b + b = a b + 2b \implies b = 0$.

---

\textbf{Шаг 3. Рассмотрим два случая}

\textbf{Случай 1: } $a = 0$

Тогда $f(n) = b$. Так как $b = 0$, получаем

\[

f(n) = 0.

\]

\textbf{Случай 2: } $a = 1$

Тогда $f(n) = n + b$. Так как $b = 0$, получаем

\[

f(n) = n.

\]

---

\textbf{Шаг 4. Проверка решений}

1. $f(n) = 0$:

\[

f(m + f(n)) = f(m + 0) = 0, \quad f(f(m)) + f(n) = 0 + 0 = 0.

\]

2. $f(n) = n$:

\[

f(m + f(n)) = f(m+n) = m+n, \quad f(f(m)) + f(n) = f(m) + n = m+n.

\]

Оба решения удовлетворяют исходному уравнению.

---

\textbf{Ответ:}

\[

\boxed{f(n) = 0 \quad \text{или} \quad f(n) = n.}

\]