Городская олимпиада по математике среди физ-мат школ г. Алматы, 2017 год

Найдите все функции $f:\mathbb{N}\to \mathbb{N}$, удовлетворяющие следующим условиям:
(a) существует бесконечно много попарно различных конечных множеств $S$ таких, что для любого $k\in S$, $f\left( k \right)$ также $\in S$;
(b) для любых различных $m,n\in \mathbb{N}.$
$m-n | f\left( m \right)-f\left( n \right)$. (Знак «|» означает делит; по другому, если $a|b$, то $b$ делится на $a$.) ( Ильясов С. )

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

Комментарии от администратора Комментарии от администратора №1.     Ответ: $f\left( n \right)=n, f\left( n \right)=const$.
1) Для каждого конечного множества $S$ рассмотрим максимальный его элемент $k$. Для него $f\left( k \right)\le k$.
Все множества $S$ не могут быть ограничены сверху, т.к. тогда было бы конечное число их различных вариантов, значит существует такая бесконечная возрастающая последовательность элементов $k$, что $f\left( k \right)\le k$.
Лемма 1. Если существует бесконечно много элементов $k$, что $f\left( k \right)=k$, то $f\left( n \right)=n$ для всех $n$.
Доказательство. Если существует $f\left( n \right)\ne n$, то $k-n | k-f\left( n \right)$, т.е. для всех достаточно больших $k$, $k-f\left( n \right)\ge 2\left( k-n \right)$ или $2n-f\left( n \right)\ge k$, что невозможно, т.к. правая часть не ограничена.
Лемма 2. Если существует бесконечно много элементов $k$, что $f\left( k \right)=C=const$, то $f\left( n \right)=C$ для всех $n$.
Доказательство. Если существует $f\left( n \right)\ne C$, для всех данных $k$, $k-n | f\left( k \right)-f\left( n \right)=C-f\left( n \right)\ne 0$, что невозможно, т.к. левая часть не ограничена.
2) $f\left( 1 \right)\ge 1$. Пусть существует бесконечно много таких $k$, что $f\left( k \right) < k$. Тогда найдется среди них такой элемент $k > 2f\left( 1 \right)$. Если $f\left( k \right)>f\left( 1 \right)$, то $k-1 > f\left( k \right)-1\ge f\left( k \right)-f\left( 1 \right) > 0$, если же $f\left( k \right) < f\left( 1 \right)$, то $k-1 > 2f\left( 1 \right)-1\ge f\left( 1 \right) > f\left( 1 \right)-f\left( k \right) > 0$. Оба варианта невозможны согласно (b), значит $f\left( k \right)=f\left( 1 \right)$ для бесконечного количества достаточно больших $k$, см. Лемму 2.
3) Это означает, что для всех достаточно больших $k$, $f\left( k \right)=k$, см. Лемму 1.