Problem 6

The sequence

a_1,a_2,\dots

of integers satisfies the conditions: (i)

1\le a_j\le 2015

for all

j\ge1

; (ii)

k+a_k\ne \ell+a_\ell

for all

1\le k<\ell

. Prove that there exist two positive integers

b

and

N

for which

\left|\sum_{j=m+1}^{n}(a_j-b)\right|\le 1007^2

for all integers

m

and

n

such that

n>m\ge N

Step 6 of 6: Combining the two boundaries and optimizing over

b

Previous step Next step

In plain words

The difference of two such overshoot sums, at $n$ and at $m$ , is controlled by $(b-1)(2015-b)$ , which AM-GM caps at $1007^2$ .

\left|\sum_{j=m+1}^{n}(a_j-b)\right|\le (b-1)(2015-b)\le 1007^2

Detailed analysis

By the previous step, both the overshoot sum at $t=n$ and the one at $t=m$ lie in the interval $\big[b(b+1)/2,\ b(4031-b)/2\big]$ , so their difference (which by Step 4 equals $\sum_{j=m+1}^n(a_j-b)$ ) is bounded in absolute value by the width of that interval, $(b-1)(2015-b)$ . By AM-GM, $(b-1)(2015-b)\le\left(\frac{(b-1)+(2015-b)}2\right)^2=1007^2$ , with equality when $b=1008$ . Whatever the actual number of chains $b\in\{1,\dots,2015\}$ turns out to be, this same inequality $(b-1)(2015-b)\le1007^2$ applies, so $\left|\sum_{j=m+1}^n(a_j-b)\right|\le1007^2$ for all $n>m\ge N$ , as required.