IMO 2015 · Problem 6

The sequence \(a_1,a_2,\ldots\) of integers satisfies the following conditions:

(i) \(1 \leq a_j \leq 2015\) for all \(j \geq 1\);

(ii) \(k+a_k \neq \ell+a_\ell\) for all \(1 \leq k < \ell\).

Prove that there exist two positive integers \(b\) and \(N\) such that \[ \left|\sum_{j=m+1}^{n}(a_j-b)\right| \leq 1007^2 \] for all integers \(m\) and \(n\) satisfying \(n>m\geq N\).

Official text of the problem. Official problem paper (PDF)

Solution

Put \(M=2015\) and define \(f(j)=j+a_j\) for every positive integer \(j\). The assumptions say that \(f\) is injective and \[ j+1\leq f(j)\leq j+M. \]

Let \(H\) be the set of positive integers that are not values of \(f\). For every integer \(t\geq M\), the \(t-M\) distinct numbers \[ f(1),f(2),\ldots,f(t-M) \] all belong to \(\{1,\ldots,t\}\). Thus at most \(M\) integers in \(\{1,\ldots,t\}\) belong to \(H\). Consequently, \(H\) is finite and \(|H|\leq M\). Also \(1\in H\), since \(f(j)>j\geq1\).

We may therefore choose the positive integers \[ b=|H|,\qquad N=\max H. \] In particular, \(1\leq b\leq M\), and every integer greater than \(N\) is a value of \(f\).

For each integer \(n\geq N\), define \[ T_n=\{f(j):1\leq j\leq n,\ f(j)>n\}. \] Exactly \(n-b\) integers in \(\{1,\ldots,n\}\) are values of \(f\). Each of their preimages is less than its value, hence belongs to \(\{1,\ldots,n\}\). Since \(f(1),\ldots,f(n)\) are distinct, it follows that \[ |T_n|=b. \] Moreover, \[ T_n\subseteq\{n+1,\ldots,n+M\}. \] The number \(n+1\) belongs to \(T_n\): it is greater than \(N\), so it equals \(f(j)\) for some \(j\), and \(j<f(j)=n+1\) implies \(j\leq n\).

Define \[ Q_n=\sum_{t\in T_n}(t-n). \] We first relate these quantities to the desired sums. For \(n\geq N\), \[ T_{n+1}=\bigl(T_n\setminus\{n+1\}\bigr)\cup\{f(n+1)\}. \] The new element is distinct from all preceding values by injectivity. Removing \(n+1\) removes a contribution of \(1\) from \(Q_n\), and replacing \(n\) by \(n+1\) decreases each of the remaining \(b-1\) contributions by \(1\). The new element contributes \(a_{n+1}\). Therefore, \[ Q_{n+1}=Q_n-b+a_{n+1}. \] Telescoping gives, for all \(n>m\geq N\), \[ \sum_{j=m+1}^{n}(a_j-b)=Q_n-Q_m. \tag{1} \]

It remains to bound the range of \(Q_n\). Write the elements of \(\{t-n:t\in T_n\}\) in increasing order as \[ 1=r_1<r_2<\cdots<r_b\leq M. \] For every \(i\), distinctness gives \(r_i\geq i\). Also, the \(b-i\) larger elements require \[ r_i\leq M-(b-i)=M-b+i. \] Since \(r_1=1\), we obtain \[ 0\leq Q_n-\frac{b(b+1)}2 =\sum_{i=2}^{b}(r_i-i) \leq (b-1)(M-b). \] This also holds when \(b=1\), with an empty sum. Thus all the \(Q_n\), for \(n\geq N\), lie in one interval of length \((b-1)(M-b)\). By (1), \[ \left|\sum_{j=m+1}^{n}(a_j-b)\right| \leq (b-1)(M-b). \] Finally, using \(M=2015\), \[ (b-1)(2015-b) =1007^2-(b-1008)^2 \leq1007^2. \] This proves the required inequality for every \(n>m\geq N\).

The solution was checked against the official IMO shortlist solutions.