29-я Балканская математическая олимпиадаАнталья, Турция, 2012 год

Найдите все функции $f: \mathbb{N} \to \mathbb{N}$, удовлетворяющие следующим условиям одновременно:
(i) $ f(n!)=f(n)! $ для любого натурального $n$;
(ii) $f(m)-f(n)$ делится на $m-n$ для любых различных натуральных $m$ и $n$.

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

Answer. $f \equiv 1, f \equiv 2, f (x) \equiv x.$

Proof. Рассмотрим два случая на ограниченность $f$.

Case 1. $f$ ограничена сверху.

Тогда найдется некоторое фиксированное $m,$ что $f(x) = m$ для бесконечного количества значений $x$. Зафиксировав любое $n \in \mathbb N$ получим, что

$$ x - n \mid f(x) - f(n) = m - f(n) \implies x - n \mid m - f(n). $$

Рассмотрев достаточно большое значение $x$ получим, что $m = f(n), \forall n \in \mathbb N$. Из первого условия $m! = m \iff m \le 2$. Отсюда получаем ответы $f \equiv 2$ и $f \equiv 1$.

Case 2. $f$ не ограничена сверху.

Claim 1. Для любого $n$ верно, что $n \mid f(n)$.

Proof. Снова зафиксируем $n$ и рассмотрим такое $x,$ что $f(x) \ge n$ и $x \ge n$:

$$ f(x)! - f(n) = f(x!) - f(n) \ \vdots \ x! - n \ \vdots \ n $$

но поскольку $n \mid f(x)!$, то $n \mid f(n), \forall n \in \mathbb N.$ $\square$

Claim 2. $f(p-2) = p-2$ для любого простого $p \ge 5$.

Proof. Из $f(1) = f(1!) = f(1)! \implies f(1) \le 2$. По теореме Вильсона заметим, что

$$ p \mid (p-2)! - 1 \mid f((p-2)!) - f(1) = f(p-2)! - f(1).$$

$\bullet$ Если $f(p-2) \ge 2(p-2) > p,$ то $p \mid f(p-2)! \implies p \mid f(1) \le 2 < p$, противоречие.

$\bullet$ Если $2(p-2) > f(p-2) \ \vdots \ p-2$, то $f(p-2) = p-2.$ $\square$

Осталось только заметить, что

$$f(p-2) - f(n) \ \vdots \ (p-2) - n \implies n - f(n) \ \vdots \ (p-2) - n$$

для всех $p \in \mathbb P_{\ge 5}$ (в частности для такого простого, что $(p-2) - n > |n-f(n)|$), откуда $f(n) = n, \forall n \in \mathbb N.$ $\blacksquare$