14th USAMO 1985

0 < a₁ ≤ a₂ ≤ a₃ ≤ ... is an unbounded sequence of integers. Let b_n = m if a_m is the first member of the sequence to equal or exceed n. Given that a₁₉ = 85, what is the maximum possible value of a₁ + a₂ + ... + a₁₉ + b₁ + b₂ + ... + b₈₅?

Solution

We show that the only possible value of the sum is 85.20 = 1700.

That is certainly the value if all a_i = 85, for then all b_j = 1 and so the sum is 19·85 + 85·1 = 85·20. Now consider the general case. Suppose that we increase some a_i by 1 from k to k+1 (whilst preserving the property that a_i is increasing, so we must have a_i < a_i+1 before the increase). The effect of the increase is to change b_k+1 from i+1 to i, but not to change any other b_j. This is obvious if a_i-1 < a_i and a_i+1 > a_i + 1. If a_i-1 = a_i, then before the change b_k = i-1 (not i) and that is still true after the change. Equally, if a_i = a_i+1 after the change, then it is still true that b_k+1 changes from i+1 to i. Thus the overall effect of the increase is not to change the sum of the a_i plus the sum of the b_j. But by a series of such changes we convert any initial sequence to all a_i = 85.

14th USAMO 1985

© John Scholes
jscholes@kalva.demon.co.uk
26 Aug 2002