### 10th USAMO 1981

Problem 5

Show that for any positive real x, [nx] ≥ ∑1n [kx]/k.

Solution

If x is an integer, then we have equality. So it is sufficient to prove the result for 0 < x < 1. The rhs only increases at x = a/b, where a, b are coprime positive integers with 1 ≤ b ≤ n, and 0 ≤ a ≤ b. So it is sufficient to consider x of this form. In fact we can assume 0 < a < b since the equality is obvious for x = 0 or 1. We may write:
a = q1b + r1
2a = q2b + r2
3a = q3b + r3
...
na = qnb + rn
with each 0 ≤ ri < b.

Thus kx = qk and we have to prove that q1 + q2/2 + ... + qn/n ≤ qn.

We claim that r1, r2, ... , rb-1 is just a permutation of 1, 2, ... , b-1. For if ri = rj with i < j, then (j - i)a = (qj - qi)b, but a and b are coprime and j - i < b, so that is impossible. So we may use the rearrangement inequality to give r1/1 + r2/2 + ... + rb-1/b-1 ≥ 1/1 + 2/2 + ... + (b-1)/(b-1) = b-1. The inequality remains true if we add some positive terms to the lhs, so we have r1/1 + r2/2 + ... + rn/n ≥ b-1. Hence r1/b + r2/(2b) + ... + rn/(nb) ≥ (b-1)/b.

So (q1 + q2/2 + ... + qn/n) + (b-1)/b ≤ (q1 + r1/b) + (q2 + r2/(2b) ) + ... (qn + rn/(nb) ) = a/b + a/b + ... + a/b = na/b = (qnb + rn)/b ≤ qn + (b-1)/b. Subtracting (b-1)/b from both sides gives the required result.

Comment. This is unusually hard for an early USAMO question.

The rearrangement inequality states that if we consider all possible sums a1b1 + a2b2 + ... + anbn where we can permute the two sequences ai and bi separately, then we get the largest sum when they are sorted the same way and the smallest when they are oppositely sorted (one increasing and one decreasing).