IMO 2006 Shortlisted Problems

Let $g(n)=nf(n)$ for $n\ge 1$ and $g(0)=0$. We note that, for $k=1,\dots ,n$, $$\lfloor \frac{n}{k}\rfloor -\lfloor \frac{n-1}{k}\rfloor =0$$ if $k$ is not a divisor of $n$ and $$\lfloor \frac{n}{k}\rfloor -\lfloor \frac{n-1}{k}\rfloor =1$$ if $k$ divides $n$. It therefore follows that if $d(n)$ is the number of positive divisors of $n\ge 1$ then $$\begin{array}{rl}g(n)& =\lfloor \frac{n}{1}\rfloor +\lfloor \frac{n}{2}\rfloor +\cdots +\lfloor \frac{n}{n-1}\rfloor +\lfloor \frac{n}{n}\rfloor \\ & =\lfloor \frac{n-1}{1}\rfloor +\lfloor \frac{n-1}{2}\rfloor +\cdots +\lfloor \frac{n-1}{n-1}\rfloor +\lfloor \frac{n-1}{n}\rfloor +d(n)\\ & =g(n-1)+d(n)\end{array}$$ Hence $$g(n)=g(n-1)+d(n)=g(n-2)+d(n-1)+d(n)=\cdots =d(1)+d(2)+\cdots +d(n)$$ meaning that $$f(n)=\frac{d(1)+d(2)+\cdots +d(n)}{n}.$$ In other words, $f(n)$ is equal to the arithmetic mean of $d(1),d(2),\dots ,d(n)$. In order to prove the claims, it is therefore sufficient to show that $d(n+1)>f(n)$ and $d(n+1)<f(n)$ both hold infinitely often.

We note that $d(1)=1$. For $n>1,d(n)\ge 2$ holds, with equality if and only if $n$ is prime. Since $f(6)=7/3>2$, it follows that $f(n)>2$ holds for all $n\ge 6$.

Since there are infinitely many primes, $d(n+1)=2$ holds for infinitely many values of $n$, and for each such $n\ge 6$ we have $d(n+1)=2<f(n)$. This proves claim (b).

To prove (a), notice that the sequence $d(1),d(2),d(3),\dots$ is unbounded (e. g. $d\left(2^k\right)=k+1$ for all $k$ ). Hence $d(n+1)>\max \{d(1),d(2),\dots ,d(n)\}$ for infinitely many $n$. For all such $n$, we have $d(n+1)>f(n)$. This completes the solution.