56th International Mathematical Olympiad Shortlisted Problems

We split the solution into three steps. In the first of them, we show that the function $f$ is injective and explain how this leads to a useful visualization of $f$. Then comes the second step, in which most of the work happens: its goal is to show that for any $n\in {\mathbb{Z}}_{>0}$ the sequence $n,f(n),f^2(n),\dots$ is an arithmetic progression. Finally, in the third step we put everything together, thus solving the problem.

Step 1. We commence by checking that $f$ is injective. For this purpose, we consider any $m,k\in {\mathbb{Z}}_{>0}$ with $f(m)=f(k)$. By (i), every positive integer $n$ has the property that $$\frac{k-m}{n}=\frac{f^n(m)-m}{n}-\frac{f^n(k)-k}{n}$$ is a difference of two integers and thus integral as well. But for $n=|k-m|+1$ this is only possible if $k=m$. Thereby, the injectivity of $f$ is established.

Now recall that due to condition (ii) there are finitely many positive integers $a_1,\dots ,a_k$ such that ${\mathbb{Z}}_{>0}$ is the disjoint union of $\left\{a_1,\dots ,a_k\right\}$ and $\left\{f(n)\mid n\in {\mathbb{Z}}_{>0}\right\}$. Notice that by plugging $n=1$ into condition (i) we get $f(m)>m$ for all $m\in {\mathbb{Z}}_{>0}$.

We contend that every positive integer $n$ may be expressed uniquely in the form $n=f^j\left(a_i\right)$ for some $j⩾0$ and $i\in \{1,\dots ,k\}$. The uniqueness follows from the injectivity of $f$. The existence can be proved by induction on $n$ in the following way. If $n\in \left\{a_1,\dots ,a_k\right\}$, then we may take $j=0$; otherwise there is some $n^{\prime }<n$ with $f\left(n^{\prime }\right)=n$ to which the induction hypothesis may be applied.

The result of the previous paragraph means that every positive integer appears exactly once in the following infinite picture, henceforth referred to as "the Table":

$a_1$	$f\left(a_1\right)$	$f^2\left(a_1\right)$	$f^3\left(a_1\right)$	$\dots$
$a_2$	$f\left(a_2\right)$	$f^2\left(a_2\right)$	$f^3\left(a_2\right)$	$\dots$
$⋮$	$⋮$	$⋮$	$⋮$
$a_k$	$f\left(a_k\right)$	$f^2\left(a_k\right)$	$f^3\left(a_k\right)$	$\dots$

The Table

Step 2. Our next goal is to prove that each row of the Table is an arithmetic progression. Assume contrariwise that the number $t$ of rows which are arithmetic progressions would satisfy $0⩽t<k$. By permuting the rows if necessary we may suppose that precisely the first $t$ rows are arithmetic progressions, say with steps $T_1,\dots ,T_t$. Our plan is to find a further row that is "not too sparse" in an asymptotic sense, and then to prove that such a row has to be an arithmetic progression as well.

Let us write $T=\mathrm{lcm}\left(T_1,T_2,\dots ,T_t\right)$ and $A=\max \left\{a_1,a_2,\dots ,a_t\right\}$ if $t>0$; and $T=1$ and $A=0$ if $t=0$. For every integer $n⩾A$, the interval ${\Delta }_n=[n+1,n+T]$ contains exactly $T/T_i$ elements of the $i^{\text{th}}$ row $(1⩽i⩽t)$. Therefore, the number of elements from the last $(k-t)$ rows of the Table contained in ${\Delta }_n$ does not depend on $n⩾A$. It is not possible that none of these intervals ${\Delta }_n$ contains an element from the $k-t$ last rows, because infinitely many numbers appear in these rows. It follows that for each $n⩾A$ the interval ${\Delta }_n$ contains at least one member from these rows.

This yields that for every positive integer $d$, the interval $[A+1,A+(d+1)(k-t)T]$ contains at least $(d+1)(k-t)$ elements from the last $k-t$ rows; therefore, there exists an index $x$ with $t+1⩽x⩽k$, possibly depending on $d$, such that our interval contains at least $d+1$ elements from the $x^{\text{th}}$ row. In this situation we have $$f^d\left(a_x\right)⩽A+(d+1)(k-t)T$$ Finally, since there are finitely many possibilities for $x$, there exists an index $x⩾t+1$ such that the set $$X=\left\{d\in {\mathbb{Z}}_{>0}\mid f^d\left(a_x\right)⩽A+(d+1)(k-t)T\right\}$$ is infinite. Thereby we have found the "dense row" promised above.

By assumption (i), for every $d\in X$ the number $${\beta }_d=\frac{f^d\left(a_x\right)-a_x}{d}$$ is a positive integer not exceeding $$\frac{A+(d+1)(k-t)T}{d}⩽\frac{Ad+2d(k-t)T}{d}=A+2(k-t)T$$ This leaves us with finitely many choices for ${\beta }_d$, which means that there exists a number $T_x$ such that the set $$Y=\left\{d\in X\mid {\beta }_d=T_x\right\}$$ is infinite. Notice that we have $f^d\left(a_x\right)=a_x+d\cdot T_x$ for all $d\in Y$.

Now we are prepared to prove that the numbers in the $x^{\text{th}}$ row form an arithmetic progression, thus coming to a contradiction with our assumption. Let us fix any positive integer $j$. Since the set $Y$ is infinite, we can choose a number $y\in Y$ such that $y-j>\left|f^j\left(a_x\right)-\left(a_x+j{T}_x\right)\right|$. Notice that both numbers $$f^y\left(a_x\right)-f^j\left(a_x\right)=f^{y-j}\left(f^j\left(a_x\right)\right)-f^j\left(a_x\right)\text{ and }{f}^y\left(a_x\right)-\left(a_x+j{T}_x\right)=(y-j)T_x$$ are divisible by $y-j$. Thus, the difference between these numbers is also divisible by $y-j$. Since the absolute value of this difference is less than $y-j$, it has to vanish, so we get $f^j\left(a_x\right)=a_x+j\cdot T_x$.

Hence, it is indeed true that all rows of the Table are arithmetic progressions.

Step 3. Keeping the above notation in force, we denote the step of the $i^{\text{th}}$ row of the table by $T_i$. Now we claim that we have $f(n)-n=f(n+T)-(n+T)$ for all $n\in {\mathbb{Z}}_{>0}$, where $$T=\mathrm{lcm}\left(T_1,\dots ,T_k\right)$$ To see this, let any $n\in {\mathbb{Z}}_{>0}$ be given and denote the index of the row in which it appears in the Table by $i$. Then we have $f^j(n)=n+j\cdot T_i$ for all $j\in {\mathbb{Z}}_{>0}$, and thus indeed $$f(n+T)-f(n)=f^{1+T/T_i}(n)-f(n)=\left(n+T+T_i\right)-\left(n+T_i\right)=T.$$ This concludes the solution.