Show that for any positive real x, [nx] ≥ ∑_{1}^{n} [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_{1}b + r_{1}

2a = q_{2}b + r_{2}

3a = q_{3}b + r_{3}

...

na = q_{n}b + r_{n}

with each 0 ≤ r_{i} < b.

Thus kx = q_{k} and we have to prove that q_{1} + q_{2}/2 + ... + q_{n}/n ≤ q_{n}.

We claim that r_{1}, r_{2}, ... , 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}/1 + r_{2}/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}/1 + r_{2}/2 + ... + r_{n}/n ≥ b-1. Hence r_{1}/b + r_{2}/(2b) + ... + r_{n}/(nb) ≥ (b-1)/b.

So (q_{1} + q_{2}/2 + ... + q_{n}/n) + (b-1)/b ≤ (q_{1} + r_{1}/b) + (q_{2} + r_{2}/(2b) ) + ... (q_{n} + r_{n}/(nb) ) = a/b + a/b + ... + a/b = na/b = (q_{n}b + 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 _{1}b_{1} + a_{2}b_{2} + ... + a_{n}b_{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).*

© John Scholes

jscholes@kalva.demon.co.uk

21 Aug 2002