56th International Mathematical Olympiad Shortlisted Problems

We visualize the set of positive integers as a sequence of points. For each $n$ we draw an arrow emerging from $n$ that points to $n+a_n$; so the length of this arrow is $a_n$. Due to the condition that $m+a_m\ne n+a_n$ for $m\ne n$, each positive integer receives at most one arrow. There are some positive integers, such as 1, that receive no arrows; these will be referred to as starting points in the sequel. When one starts at any of the starting points and keeps following the arrows, one is led to an infinite path, called its ray, that visits a strictly increasing sequence of positive integers. Since the length of any arrow is at most 2015, such a ray, say with starting point $s$, meets every interval of the form $[n,n+2014]$ with $n⩾s$ at least once.

Suppose for the sake of contradiction that there would be at least 2016 starting points. Then we could take an integer $n$ that is larger than the first 2016 starting points. But now the interval $[n,n+2014]$ must be met by at least 2016 rays in distinct points, which is absurd. We have thereby shown that the number $b$ of starting points satisfies $1⩽b⩽2015$. Let $N$ denote any integer that is larger than all starting points. We contend that $b$ and $N$ are as required.

To see this, let any two integers $m$ and $n$ with $n>m⩾N$ be given. The sum ${\sum }_{i=m+1}^n{a}_i$ gives the total length of the arrows emerging from $m+1,\dots ,n$. Taken together, these arrows form $b$ subpaths of our rays, some of which may be empty. Now on each ray we look at the first number that is larger than $m$; let $x_1,\dots ,x_b$ denote these numbers, and let $y_1,\dots ,y_b$ enumerate in corresponding order the numbers defined similarly with respect to $n$. Then the list of differences $y_1-x_1,\dots ,y_b-x_b$ consists of the lengths of these paths and possibly some zeros corresponding to empty paths. Consequently, we obtain $$\sum _{i=m+1}^n{a}_i=\sum _{j=1}^b\left(y_j-x_j\right)$$ whence $$\sum _{i=m+1}^n\left(a_i-b\right)=\sum _{j=1}^b\left(y_j-n\right)-\sum _{j=1}^b\left(x_j-m\right)$$ Now each of the $b$ rays meets the interval $[m+1,m+2015]$ at some point and thus $x_1-m,\dots ,x_b-m$ are $b$ distinct members of the set $\{1,2,\dots ,2015\}$. Moreover, since $m+1$ is not a starting point, it must belong to some ray; so 1 has to appear among these numbers, wherefore $$1+\sum _{j=1}^{b-1}(j+1)⩽\sum _{j=1}^b\left(x_j-m\right)⩽1+\sum _{j=1}^{b-1}(2016-b+j)$$ The same argument applied to $n$ and $y_1,\dots ,y_b$ yields $$1+\sum _{j=1}^{b-1}(j+1)⩽\sum _{j=1}^b\left(y_j-n\right)⩽1+\sum _{j=1}^{b-1}(2016-b+j)$$ So altogether we get $$\begin{array}{c}\left|\sum _{i=m+1}^n\left(a_i-b\right)\right|⩽\sum _{j=1}^{b-1}((2016-b+j)-(j+1))=(b-1)(2015-b)\\ ⩽{\left(\frac{(b-1)+(2015-b)}{2}\right)}^2=1007^2\end{array}$$ as desired.

Solution 2:

Set $s_n=n+a_n$ for all positive integers $n$. By our assumptions, we have $$n+1⩽s_n⩽n+2015$$ for all $n\in {\mathbb{Z}}_{>0}$. The members of the sequence $s_1,s_2,\dots$ are distinct. We shall investigate the set $$M={\mathbb{Z}}_{>0}\backslash \left\{s_1,s_2,\dots \right\}$$ Claim. At most 2015 numbers belong to $M$.

Proof. Otherwise let $m_1<m_2<\cdots <m_{2016}$ be any 2016 distinct elements from $M$. For $n=m_{2016}$ we have $$\left\{s_1,\dots ,s_n\right\}\cup \left\{m_1,\dots ,m_{2016}\right\}\subseteq \{1,2,\dots ,n+2015\}$$ where on the left-hand side we have a disjoint union containing altogether $n+2016$ elements. But the set on the right-hand side has only $n+2015$ elements. This contradiction proves our claim. $\square$

Now we work towards proving that the positive integers $b=|M|$ and $N=\max (M)$ are as required. Recall that we have just shown $b⩽2015$.

Let us consider any integer $r⩾N$. As in the proof of the above claim, we see that $$\begin{array}{c}{B}_r=M\cup \left\{s_1,\dots ,s_r\right\}\end{array}\text{\hspace{1em}(1)}$$ is a subset of $[1,r+2015]\cap \mathbb{Z}$ with precisely $b+r$ elements. Due to the definitions of $M$ and $N$, we also know $[1,r+1]\cap \mathbb{Z}\subseteq B_r$. It follows that there is a set $C_r\subseteq \{1,2,\dots ,2014\}$ with $\left|C_r\right|=b-1$ and $$\begin{array}{c}{B}_r=([1,r+1]\cap \mathbb{Z})\cup \left\{r+1+x\mid x\in C_r\right\}.\end{array}\text{\hspace{1em}(2)}$$ For any finite set of integers $J$ we denote the sum of its elements by $\sum J$. Now the equations (1) and (2) give rise to two ways of computing $\sum B_r$ and the comparison of both methods leads to $$\sum M+\sum _{i=1}^r{s}_i=\sum _{i=1}^{r}i+b(r+1)+\sum C_r$$ or in other words to $$\begin{array}{c}\sum M+\sum _{i=1}^r\left(a_i-b\right)=b+\sum C_r\end{array}\text{\hspace{1em}(3)}$$ After this preparation, we consider any two integers $m$ and $n$ with $n>m⩾N$. Plugging $r=n$ and $r=m$ into (3) and subtracting the estimates that result, we deduce $$\sum _{i=m+1}^n\left(a_i-b\right)=\sum C_n-\sum C_m$$ Since $C_n$ and $C_m$ are subsets of $\{1,2,\dots ,2014\}$ with $\left|C_n\right|=\left|C_m\right|=b-1$, it is clear that the absolute value of the right-hand side of the above inequality attains its largest possible value if either $C_m=\{1,2,\dots ,b-1\}$ and $C_n=\{2016-b,\dots ,2014\}$, or the other way around. In these two cases we have $$\left|\sum C_n-\sum C_m\right|=(b-1)(2015-b),$$ so in the general case we find $$\left|\sum _{i=m+1}^n\left(a_i-b\right)\right|⩽(b-1)(2015-b)⩽{\left(\frac{(b-1)+(2015-b)}{2}\right)}^2=1007^2$$ as desired.