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 2 of 6: The arrows partition into at most

2015

ascending chains

Previous step Next step

In plain words

Following the arrows from any starting point traces out an increasing chain, and every positive integer lies on exactly one such chain.

\mathbb{Z}_{>0}=c_1\sqcup c_2\sqcup\dots\sqcup c_b,\qquad b\le 2015

Detailed analysis

Draw an arrow from $k$ to $f(k)=k+a_k$ for each $k\ge1$ . Since $f$ is injective, every positive integer has at most one arrow pointing into it, so following the arrows forward and backward from any point traces out an ascending chain, terminating backward only at the finitely many start-points with no arrow pointing in. Together these chains partition the positive integers into $b$ disjoint ascending chains $c_1,\dots,c_b$ , each skipping forward by at most $2015$ per step. There are at most $2015$ chains, since among any $2015$ consecutive positive integers every chain must contain at least one element (as gaps between consecutive elements of one chain are at most $2015$ ), so at most $2015$ chains can fit.