14th USAMO 1985 Problem 5 0 < a 1 ≤ a 2 ≤ a 3 ≤ ... 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 19 = 85, what is the maximum possible value of a 1 + a 2 + ... + a 19 + b 1 + b 2 + ... + b 85 ?
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. 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