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

Келесі шарттарды қанағаттандыратын барлық $f:\mathbb{N}\rightarrow\mathbb{N}$ функцияларын табыңыз:
(а) кез-келген $k\in S$ үшін, $f\left(k\right)\in S$ болатындай шексіз көп әртүрлі ақырлы $S$ жиындары табылады;
(b) кез-келген әртүрлі $m,n\in\mathbb{N}$ үшін $m-n\ \ |\ \ f\left(m\right)-f(n).$
(«|» бөледі дегенді білдіреді; басқаша айтқанда: $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.