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 1 of 6: The map

k\mapsto k+a_k

never repeats

Previous step Next step

In plain words

Condition (ii) is exactly the statement that no two indices map to the same value.

f(k)=k+a_k\ \text{is injective on the positive integers}

Detailed analysis

Condition (ii), $k+a_k\ne\ell+a_\ell$ for $k\ne\ell$ , says precisely that the map $f(k)=k+a_k$ is injective on the positive integers. Since $1\le a_k\le2015$ , we have $f(k)\in\{k+1,\dots,k+2015\}$ : each arrow $k\mapsto f(k)$ jumps forward by at most $2015$ .