29-th Balkan Mathematical Olympiad

There are three functions: the constant functions $1$, $2$ and the identity function ${\text{id}}_{{\mathbb{Z}}^{+}}$. These functions clearly satisfy the conditions in the hypothesis. Let us prove that there are only ones.

Consider such a function $f$ and suppose that it has a fixed point $a\ge 3$, that is $f(a)=a$. Then $a!$, $(a!)!$, ... are all fixed points of $f$, hence the function $f$ has a strictly increasing sequence $a_1<a_2<\cdots <a_k<\dots$ of fixed points. For a positive integer $n$, $a_k-n$ divides $a_k-f(n)=f(a_k)-f(n)$ for every $k\in {\mathbb{Z}}^{+}$. Also $a_k-n$ divides $a_k-n$, so it divides $a_k-f(n)-(a_k-n)=n-f(n)$. This is possible only if $f(n)=n$, hence in this case we get $f={\text{id}}_{{\mathbb{Z}}^{+}}$.

Now suppose that has no fixed points greater than $2$. Let $p\ge 5$ be a prime and notice that by Wilson's Theorem we have $(p-2)!\equiv 1(\mathrm{mod}p)$. Therefore $p$ divides $(p-2)!-1$. But $(p-2)!-1$ divides $f((p-2)!)-f(1)$, hence $p$ divides $$f((p-2)!)-f(1)=(f(p-2))!-f(1).$$ Clearly we have $f(1)=1$ or $f(1)=2$. As $p\ge 5$, the fact that $p$ divides $(f(p-2))!-f(1)$ implies that $f(p-2)<p$. It is easy to check, again by Wilson's Theorem, that $p$ does not divide $(p-1)!-1$ and $(p-1)!-2$, hence we deduce that $f(p-2)\le p-2$. On the other hand, $p-3=(p-2)-1$ divides $f(p-2)-f(1)\le (p-2)-1$. Thus either $f(p-2)=f(1)$ or $f(p-2)=p-2$. As $p-2\ge 3$, the last case is excluded, since the function $f$ has no fixed points greater than $2$. It follows $f(p-2)=f(1)$ and this property holds for all primes $p\ge 5$.

Taking $n$ any positive integer, we deduce that $p-2-n$ divides $f(p-2)-f(n)=f(1)-f(n)$ for all primes $p\ge 5$. Thus $f(n)=f(1)$, hence $f$ is the constant function $1$ or $2$.

---

Alternative solution.

Note first that if $f(n_c)=n_c$, then $m-n_c|f(m)-m$ for all $m\in {\mathbb{Z}}^{+}$. If $f(n_c)=n_c$ for infinitely many $n_c\in {\mathbb{Z}}^{+}$, then $f(m)-m$ has infinitely many divisors, hence $f(m)=m$ for all $m\in {\mathbb{Z}}^{+}$. On the other hand, if $f(n_c)=n_c$ for some $n_c\ge 3$, then each term of the sequence $(n_k{)}_{k=0}^{n_c}$, which is recursively defined by $n_k=n_{k-1}!$. Hence if $f(3)=3$, then $f(n)=n$ for all $n\in {\mathbb{Z}}^{+}$.

We may assume that $f(3)\ne 3$. Since $f(1)=f(1)!$, and $f(2)=f(2)!$, $f(1),f(2)\in \{1,2\}$. We have $4=3!-2|f(3)!-f(2)$. This together with $f(3)\ne 3$ implies that $f(3)\in \{1,2\}$. Let $n>3$, then $n!-3|f(n)!-f(3)$ and $3|f(n)!$, i.e. $f(n)!\in \{1,2\}$. Hence we conclude that $f(n)\in \{1,2\}$ for all $n\in {\mathbb{Z}}^{+}$.

If $f$ is not constant, then there exist positive integers $m,n$ with $\{f(m),f(n)\}=\{1,2\}$. Let $k=2+\max \{m,n\}$. If $f(k)\ne f(m)$, then $k-m|f(k)-f(m)$. This is a contradiction as $|f(k)-f(m)|=1$ and $k-m\ge 2$.

Therefore the functions satisfying the conditions are $f=1,f=2,f={\text{id}}_{{\mathbb{Z}}^{+}}$.