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 $\left\lfloor \frac{n}{d} \right\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} \left\lfloor \frac{n}{k} \right\rfloor.$$
Adding, if necessary, the term $\left\lfloor \frac{n}{n+1} \right\rfloor = 0$ at the end, we can group the terms of the sum into pairs having the sum $\left\lfloor \frac{n}{2k-1} \right\rfloor - \left\lfloor \frac{n}{2k} \right\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 $-\left\lfloor \frac{n}{2k} \right\rfloor + \left\lfloor \frac{n}{2k} \right\rfloor$.

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