## Problem 5

$0<a_{1} \leq a_{2} \leq a_{3} \leq \ldots$ 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}+\ldots+$ $\mathrm{a}_{19}+\mathrm{b}_{1}+\mathrm{b}_{2}+\ldots+\mathrm{b}_{8} ?$


## 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 \cdot 85+85 \cdot 1=85 \cdot 20$. Now consider the general case. Suppose that we increase some $\mathrm{a}_{\mathrm{i}}$ by 1 from $\mathrm{k}$ to $\mathrm{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 $\mathrm{b}_{\mathrm{k}+1}$ changes from $\mathrm{i}+1$ to $\mathrm{i}$. Thus the overall effect of the increase is not to change the sum of the $\mathrm{a}_{\mathrm{i}}$ plus the sum of the $\mathrm{b}_{\mathrm{j}}$. But by a series of such changes we convert any initial sequence to all $\mathrm{a}_{\mathrm{i}}=85$.

## 15th USAMO 1986

