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 3 of 6: Choosing

b

and

N

Previous step Next step

In plain words

Once past every chain start-point, the sum over an interval depends only on where each chain first exits it.

b:=\#\{\text{chains}\},\qquad N:=\max(\text{start-points of the chains})

Detailed analysis

Let $b$ be the number of chains $c_1,\dots,c_b$ found above, and let $N$ be the largest start-point among all chains, so that for any $t\ge N$ every chain already contains an element $\le N\le t$ . For an interval $(t_1,t_2]$ and a chain $c$ , the sum of the values $a_j=f(j)-j$ over indices $j\in c\cap(t_1,t_2]$ telescopes along the chain to $\big(\min\{x>t_2:x\in c\}-t_2\big)-\big(\min\{x>t_1:x\in c\}-t_1\big)$ .