# 1981 USAMO Problems/Problem 5

## Problem

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. 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$$