1981 USAMO Problems/Problem 5


Show that for any positive real $x$, $[nx]\ge \sum_{1}^{n}\left(\frac{[kx]}{k}\right)$

Solution(due to Pavel Zatitskiy)

First of all we write $[kx]=kx-\{kx\}$. So, we need to prove that $\sum_{1}^{n}\left(\frac{\{kx\}}{k}\right)\geq \{nx\}.$ Let's denote $a_k=\{kx\}$. It is easy to see that $a_k+a_m \geq a_{k+m}$. We need to prove $\sum_{1}^{n}\left(\frac{a_k}{k}\right)\geq a_n.$

We will prove it by induction by $n$. The base is obvious, so we need to make a step.

Let's take $m$ such that $\frac{a_m}{m}$ is minimal. If $m=n$ then our inequality is obvious. So, $m<n$. Then, by induction, $\sum_{1}^{n-m}\left(\frac{a_k}{k}\right)\geq a_{n-m}$ and $\sum_{n-m+1}^{n}\left(\frac{a_k}{k}\right)\geq m\cdot \frac{a_m}{m}=a_m$. Now we can add these two inequalities and get \[\sum_{1}^{n}\left(\frac{a_k}{k}\right) \geq a_{n-m}+a_m \geq a_n\]

See Also

1981 USAMO (ProblemsResources)
Preceded by
Problem 4
Followed by
Last Question
1 2 3 4 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png