USAMO 81/5 solution

10th USAMO 1981

Problem 5

Show that for any positive real x, [nx] ≥ ∑₁ⁿ [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 = q₁b + r₁
2a = q₂b + r₂
3a = q₃b + r₃
...
na = q_nb + r_n
with each 0 ≤ r_i < b.

Thus kx = q_k and we have to prove that q₁ + q₂/2 + ... + q_n/n ≤ q_n.

We claim that r₁, r₂, ... , r_b-1 is just a permutation of 1, 2, ... , b-1. For if r_i = r_j with i < j, then (j - i)a = (q_j - q_i)b, but a and b are coprime and j - i < b, so that is impossible. So we may use the rearrangement inequality to give r₁/1 + r₂/2 + ... + r_b-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 r₁/1 + r₂/2 + ... + r_n/n ≥ b-1. Hence r₁/b + r₂/(2b) + ... + r_n/(nb) ≥ (b-1)/b.

So (q₁ + q₂/2 + ... + q_n/n) + (b-1)/b ≤ (q₁ + r₁/b) + (q₂ + r₂/(2b) ) + ... (q_n + r_n/(nb) ) = a/b + a/b + ... + a/b = na/b = (q_nb + r_n)/b ≤ q_n + (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 a₁b₁ + a₂b₂ + ... + a_nb_n where we can permute the two sequences a_i and b_i 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).

10th USAMO 1981