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 5 of 6: Bounding the overshoot sum at a fixed boundary

Previous step Next step

In plain words

The $b$ chains next-exit points past $t$ must be distinct positive integers no larger than $2015$ , so their sum is squeezed between the $b$ smallest and $b$ largest such values.

1+2+\dots+b\ \le\ \sum_{\text{chain }c}\big(\min\{x>t:x\in c\}-t\big)\ \le\ 2015+2014+\dots+(2015-b+1)

Detailed analysis

Fix a boundary $t$ ( $=m$ or $n$ ) with $t\ge N$ . For each of the $b$ chains, $\min\{x>t:x\in c\}-t$ is a positive integer at most $2015$ (consecutive elements of one chain differ by at most $2015$ ), and these $b$ overshoot values are pairwise distinct across the $b$ chains, since a given point $x$ belongs to only one chain. Hence their sum lies between the sum of the $b$ smallest possible distinct positive values, $1+2+\cdots+b$ , and the sum of the $b$ largest possible values not exceeding $2015$ , namely $2015+2014+\cdots+(2015-b+1)$ .