THE 68th NMO SELECTION TESTS FOR THE JUNIOR BALKAN MATHEMATICAL OLYMPIAD

We count how many times a number $d$ contributes to the sum of the differences. It appears $\lfloor \frac{n}{d}\rfloor$ times; if $d$ is odd, then this term is to be added, while if $d$ is even this term is to be subtracted. Thus, the desired sum is $$\sum _{k=1}^n(-1{)}^{k+1}\lfloor \frac{n}{k}\rfloor .$$ Adding, if necessary, the term $\lfloor \frac{n}{n+1}\rfloor =0$ at the end, we can group the terms of the sum into pairs having the sum $\lfloor \frac{n}{2k-1}\rfloor -\lfloor \frac{n}{2k}\rfloor \ge 0$, hence the sum is non-negative. Similarly, separating the first term (which is equal to $n$), adding, if necessary, a $0$ term to the end, we can again group the terms into pairs having the sum $-\lfloor \frac{n}{2k}\rfloor +\lfloor \frac{n}{2k}\rfloor$.

$$\left[\frac{n}{2k+1}\right]\le 0,\text{ hence the sum is at most }n.$$