AustriaMO2011

If an infinite number of such $K$ do not exist, there must exist some $K_o$, such that for all $K>K_o$ there exists an $n$ with $n\le K<f(n)$. Since $|f(x)-x|\le 3$ must always hold, such an $n$ can only be $K$, $K-1$ or $K-2$.

The same must hold for $K=f(n)$, and so on. This means that, from some $K_o$ on, the function must map “up” into each interval $[n,f(n)]$, and also “up” out of each such interval. In order for this to be possible, we must have $f(n)-n\ge 3$, and it therefore follows that $|f(n)-n|=3$ must hold for all $n>K>K_o$. If this is the case, we have $$M(n)=\frac{1}{n+1}\sum _{j=0}^n|f(j)-j|=\frac{1}{n+1}\left(\sum _{j=0}^K|f(j)-j|+3(n-k)\right)=3-\frac{C}{n+1}$$ with $$C=3K+3-\sum _{j=0}^K|f(j)-j|=\sum _{j=0}^K(3-|f(j)-j|)\ge 0.$$ It therefore follows that there exists a $K_1$ such that $M(n)=3-\frac{C}{n+1}>2.011$ for $n>K_1$, which contradicts the assumption $M(n)<2.011$. This is not possible, and we see that an infinite number of $K$ with the required properties exist, as claimed.