ÖMO 2011 Problem 2

We consider permutations $f$ of the set $\mathbb{N}$ of non-negative integers, i.e. bijective maps $f$ from $\mathbb{N}$ to $\mathbb{N}$ , with the following additional properties: $$f(f(x)) = x \text{and} \left| f(x)-x\right| \leqslant 3 \text{for all } x \in\mathbb{N}\text{.}$$ Further, for all integers $n > 42$ , $$\left.M(n)=\frac{1}{n+1}\sum_{j=0}^n \left|f(j)-j\right|<2,011\text{.}\right.$$ Show that there are infinitely many natural numbers $K$ such that $f$ maps the set $$\left\{ n\mid 0\leqslant n\leqslant K\right\}$$ onto itself.