Saudi Arabia Mathematical Competitions 2012

The answer is all $k\ne 2$. If $k=2$, note that $f(f(n))=2n$ implies that $f(n)\ne n$ for all $n$. Therefore $f(1)\ne 1$. We also have $f(1)\ne 2$ since then $f(f(1))=f(2)=2$, so $f(1)>2$. But then $2=f(f(1))<f(1)$ while $f(1)>1$, so we have a contradiction of the second condition.

For $k=1$, we simply take $f(n)=n$. We give an algorithm to construct a function that works for any $k>2$. Note that each time we set $f(a)=b$, this implicitly means we also set $f(k^{m}a)=k^{m}b$ and $f(k^{m}b)=k^{m+1}a$. Begin by setting $f(1)=2$. Then repeat the following: for the smallest number $m$ for which $f(m)$ has yet to be defined, set $f(m)=m^{\prime }$ where $m^{\prime }$ is the smallest nonmultiple of $k$ greater than $f(m-1)$. It is clear we will obtain $f(f(n))=kn$ this way for all $n$; we now need to show $f(n)<f(n+1)$. We go by strong induction, with $n=1$ obvious. Given it is true up to $n$, we show $f(n)<f(n+1)$ with two cases:

(i) $f(n+1)$ is not a multiple of $k$: This means $n+1$ was selected as an $m$ in the algorithm, and $f(n+1)$ was deliberately set to be greater than $f(n)$.

(ii) $f(n+1)$ is a multiple of $k$: Let $x$ be the largest integer less than or equal to $n$ such that $f(x)$ is a multiple of $k$. Because all multiples of $k$ map to multiples of $k$ under $f$, we have $n-k<x\le n$. Let $f(x)=ka$ and $f(n+1)=kb$. Then $f(a)=x$ and $f(b)=n+1$. Since $x<n+1$ and $a,b<n$, the inductive hypothesis implies $a<b$. Note that for each $m\in \{n-x+1,n-x+2,\dots ,n\}$, $f(m)$ was set equal to $f(m-1)+1$. So this means that the algorithm would have set $f(n)=f(x)+(n-x)=ka+(n-x)$. Since $n-x<k$, $ka+(n-x)<k(a+1)\le kb$. Therefore $f(n)<f(n+1)$ as desired.