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

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

Page

Toolbox

Search

1981 USAMO Problems/Problem 5

Problem

Solution(due to Pavel Zatitskiy)

See Also