Solution Outline:

Replace (i) with $0\leq a_j\leq n=2014$ for convenience. Let $b_i=a_i+i$, so $i\leq b_i\leq i+n$. Then the sequence $b_i$ must contain every nonnegative integer except for $b\leq n$ of them. Let $B$ be that set of $b$ numbers. Pick any $N$ greater than all the numbers in $B$. Let $S_i=\{b_0,\ldots, b_i\}$ and $T_i=\{0,\ldots, i\}$. We shall evaluate the sum $\sum_N^{N+m} b_i$. Note that $T_{N+m}\setminus B\subset S_{N+m}\subset T_{N+m+n}\setminus B$. Since $S_{N+m}$ has exactly $N+m+1$ elements, and $T_{N+m+n}\setminus B$ has $N+m+n+1-b$, there are exactly $n-b$ elements in $T_{N+m+n}\setminus T_{N+m}$ that are NOT in $S_{N+m}$. Thus the maximum value of $\sum_N^{N+m} b_i$ is \[\sum_{N+m+n-b+1}^{N+m+n} i +\sum_{N+b}^{N+m} i \], when $m\geq b$ (If $m<b$, $\sum_N^{N+m}(a_i-b)\leq b(n-b)$ is immediate). Thus $\sum_N^{N+m}(a_i-b)=\sum_N^{N+m}(b_i-i-b)\leq b(n-b)$. For the minimum, note that each element in $S_{N}$ is $\leq N+n$, so the minimum value of $\sum_N^{N+m} b_i$ is \[\sum_{N+n+1}^{N+m+b} i + \sum_{N}^{N+n-b} i \]when $m\geq n-b$. If $m<n-b$ then $\sum_N^{N+m}(a_i-b)\geq -b(n-b)$ is immediate. Otherwise more arithmetic manipulation gives $\sum_N^{N+m}(a_i-b)\geq -b(n-b)$ again. Therefore $\left\vert\sum_N^{N+m}(a_i-b)\right\vert\leq b(n-b)\leq 1007^2$.

Interesting connection: this problems looks like it has its roots in

Solution sketch according to these ideas:

This connection is probably the origin of the problem. I have no idea who he/she is, but I'd bet that the person who proposed this problem is a

Very nice solution and interpretation from fph! This was co-authored by Ross Atkins and me (Ivan Guo) of Australia. And you are correct, Ross juggles.

silouan wrote: Thank you for the nice problem Ivan!! Could you please offer us your proposed solution? Thanks

I think it is either combinatorics or algebra. Guessing combinatorics since Q5 was algebra, but I have no idea.

Here is my solution. I will try to add tomorrow more detail if you think some parts are not obvious. the end was a bit rushed cause i need to go to sleep. I will imagine the numbers $1,2 \cdots 2015$ as some surf-boards on the sea, arranged in the same line. At each time the surf-boards can be on an wave or not. We will visualize an process on the surf boards which happens in the same time with vizualizing the sequence $a_i$. At time 1 no surf board is on an wave. If $a_1=i$ we will imagine an wave starting at point $i$ and flowing one step to the left at each time. For example: at time $1$ the wave is created. At time $2$ the wave is at bord $i-1$.. etc after it passes board $1$ it dissapears as if it would hit the shore. If $a_2=j$ at step $2 $ a new wave stars at surf board $j$. We will imagine that the creation of the wave at step $k$ occours at times $k+$ epsilon. First observation There can be no wave created at time $T$ in position $j$ if there already is an wave on position $j$ at time $T$. This is $<=>$ to $a_T \neq a_l -(T-l)$ since the last term is the cordinates of wave $l$ at time $T$ so I hope this is clear. Second obervation If at time $i$ the wave $a_i$ which if it is$ \neq1$ is created and at time $i+1$ the wave created is $a_{i+1} \neq 2015 $ , then if instead we were to create wave $a'_i=a_{i+1}+1$ at step $i$ and wave $a'_{i+1}=a_i-1$ at step $i+1$. The wave picture would look exactly the same after time $i+1+eps$, and we could continue our sequence in the same way( since the waves are the only condition we are imposed). Note the we used First observation here. And $a'_{i+1}+a'_i=a_i+a_{i+1}$. The only thing we did was make the wave, which was supposed to be the one created by $a_{i+1} $, a step early and the one created by $a_i$ a step late, but in the same position they would eventualy be. Review What we really nead is the fact that we make the wave order increasingly by this change\ Sum constant, so we don't care about the $a_{i+1} \neq 2015 $ part. By ''eventual order'' you should think as the fact that it reaches the shore at the time it was originaly intented to ! Third observation The number of waves is non-decreasing and at most 2014 at an integer time. At each $T+eps$ a new one is created and at most one dissapears. so thats it. So the number of waves is eventually always constats. Let that number of waves be $\lambda -1$ ( at an integer time, i.e just before creation and perhaps disappearance) Final step Suppose after time $N$ we always have $\lambda-1$ waves and choose $b=\lambda$. By obervation 2 $\sum_{j=m}^n(a_j)$ will be the same as $\sum_{j=m}^n(a'_j)$. Where $a'_k$ is obtained from sequence $a_i$ and is defined only for $k \in (m, \cdots n)$ by repeatedly applying observation 2. Getting the same wave picture (eventualy) and the wave created by $a'_i$ is always at the left of the wave created by $a'_{i+1}$. Now visualising this process of the $a'_i$ in $1,2 \cdots 2015$. we would have the following $a'_k\le \lambda$ at the beginning. ( at the times $T$ when we have at most a block of $ \lambda -2 $ consecutive waves at the start of $1,2 \cdots 2015$) this can only last for as much as 2014 seconds. At the middle we would have some $a'_i=\lambda$ and after some random $a'_i$'s but at most $\lambda-1 $ of them because otherwise we are going to have another $a'_i=\lambda$ ( by our wave imposed order). The bellow expressions are rewritings of \[ \sum_{j=m}^n(a_j-b) \] in the worst case. ( for example at the positive part, the obvious worst is when all $a'_i$ are 2015 after the middle part( $a'_i=\lambda$) but we can only have a few of such=2015) => We have at most $(\lambda-1)( 2015) -(\lambda-1)(\lambda)= (\lambda-1)(2015-\lambda) \le 1007^2$ positive stuff. And at most $1007^2$ negative stuff( due to beginning of $a'_i$'s) , almost the same thing as above. Hence the inequality \[\left\vert \sum_{j=m}^n(a_j-b)\right\vert\le1007^2\]. Step review Basically what this step does is to change the order of the waves, kepping the sum constant (obervation 2) so that we have waves which respect the order of i( i.e wave i is at the left of wave j if i<j) we do this so that we could observe clearely the extreme cases, as having waves in order we would have a large portion where $a'_i=\lambda$( this because after say '2014-\lambda' time we would have the only present $\lambda-1$ waves positioned at the start of $(1,2...2015)$ ) Also don't hesitate to ask if anything is unclear

This is not the first problem that is much easier for jugglers. See ISL 2005's C7 (http://www.artofproblemsolving.com/community/c6h85076p494833) for example. fph wrote: Interesting connection: this problems looks like it has its roots in

There is no reason to do that ugly shift by $1$. We are simply talking about patterns where we throw a ball at each tick. As given, the problem is exactly about juggling sequences. Then the number $b$ of balls is exactly the (asymptotic) average of the $a_n$, too (this is called the Average Theorem, to which the aforementioned C7 is a converse).

When will the official solutions be posted for IMO 2015?

I very much enjoyed oneplusone's solution in #4 by direct processing of the given information. Notice as a matter of detail that in the estimate of the minimum the lower limit of the first sum in the displayed expression is $N+n$ and the upper limit of the second sum is $N+n-b-1$. Also the special cases are $m+1<b$ and $m+1<n-b$ because $\sum_N^{N+m}$ has $m+1$ terms.

In my opinion this is an algebra problem, albeit with a strong combinatorial flavor. It was my favorite problem in this IMO

This problem reminds me of Proizvolov's Identity. https://en.wikipedia.org/wiki/Proizvolov%27s_identity I think by using this identity we might obtain a new solution. Did it occur to anybody else? Take the first 2N positive integers: 1, 2, 3, ..., 2N − 1, 2N, and partition them into two subsets of N numbers each. Arrange one subset in increasing order: $A_1$<$A_2$<$ \cdots$<$A_N$ and the other subset in decreasing order: $B_1$>$B_2$>$ \cdots$>$B_N$ Then we have the Proizvolov's Identity: $|A_1-B_1|+|A_2-B_2|+ \cdots + |A_N-B_N|$ = $N^2$

Ivan wrote: s372102 wrote: Ivan wrote: It is similar to fph's solution, but avoids the juggling language. Essentially, you separate the terms into equivalence classes (or colour them, if you like) according to the rule $a_i~a_j$ if $a_i+i=a_j$ (so each class/colour corresponds to a particular juggling ball). Now set b to be the number of classes/colours and explicitly compute/bound the required sum, first within each class/colour then altogether. The bound is $(2015-b)(b-1)$ and fph's "total ball height" interpretation is very nice. There is another alternative which is a little messy. It considers the sequence $d_i=a_i+i$, and then sort the $d_i$s in increasing order step by step by swapping $\min(d_i,d_{i+1},\ldots)$ with $d_i$. After the sorting, the new sequence $a_i=d_i-i$ still satisfies $1\leq a_i\leq 2015$ and should be eventually constant. Choose that constant to be $b$. The required sum is the difference between the original and new sequences, which can be bounded by tracking the changes caused by each swap. In particular each change is bounded by $2015-b$ and there are at most $b-1$ of them. I think it is either combinatorics or algebra. Guessing combinatorics since Q5 was algebra, but I have no idea. Could you be more specific? according to the rule $a_i~a_j$ if $a_i+i=a_j$? What if all $a_i=1$? Thanks! If $a_i=1$ for all $i$ then everything will be in the same equivalence class and then $b=1$. I see! according to the rule $a_i~a_j$ if $a_i+i=j$

Here's my writeup from the test, in all its glory with strikethroughs and so on. http://dng.northjersey.com/media_server/tr/2015/07/28math/Mathproblem.pdf

Theorem Let $T$ be a non-negative integer parameter. If given a sequence $a_1,a_2,\dots$ that satisfies the conditions: (i) $1 \le a_j \le T+1$ for all $j \ge 1;$ (ii) $k+a_k \ne \ell+a_\ell$ for all $1 \le k<\ell,$ then there exist two integers $v$ and $N$, $0 \le v \le T$ and $N>0$, for which $$\left\vert\sum_{j=m+1}^n(a_j-(v+1))\right\vert\le (T-v)\,v \le \left(\frac T 2\right)^2$$for all integers $m$ and $n$ such that $n>m\ge N$. Proof My proof is better explained using graphic interpretation. Consider the set of points on a plane: $\{(x,y) \mid x,y \in \mathbb N,\,y \le T+1\}$ (I'll call it the base strip). The sequence is represented on it by the subset $\{(i,a_i) \mid i \in \mathbb N\}$ which is painted red. Each line $L_n$ of kind $x+y=n$, where $n \ge 2$ is an integer, will be called a carrier line. Note that the condition (ii) states that each carrier line is occupied by at most one red point. Every such line with exactly one red point on it will be called occupied while the rest carriers will be called free. First, I'll prove that the set of free carriers is finite. Indeed, all the carriers $L_n$ with $2 \le n \le T+m+1$, where $m \in \mathbb N$, cover the part of the base strip having $x \le m$, so there are at least $m$ red points lying on them. Thus, the number of free carriers among them is at most $T+m-m=T$. Since $m$ is arbitrary, the total number of free cariers doesn't exceed $T$. Take $N$ such that all the carriers $L_n$ with $n \ge N+2$ are occupied. Next, take any red point and consider the points on the base strip which are lying on the point's carrier below it (i.e. having strictly greater $x$). Call it the point's trace and paint black. Finally, the set $P_x=\{\,y \mid (x,y) \text { is black}\}$ will be called a pattern, the number elements $|P_x|$ in it will be called its volume and the sum $w_x$ of all elements in $P_x$ will be called its weight. Now let $j>N$. Let's track how $P_j$, its volume and its weight change when $j$ increases by 1. Obviously $P_{j+1}$ is $P_j$ plus added $a_j$ (red point) and shifted down by $1$; a point that goes to $0$ vanishes. This means that the volume doesn't change at all. Indeed, if $1 \notin P_j$, then $a_j=1$ or the carrier $L_{j+1}$ will remain unoccupied, so one point always vanishes going to $0$, and exactly one point is added before the shift (it may be the same point). Let $v$ be this constant volume. As a pattern never contains $T+1$, $v$ ranges from $0$ to $T$. Now it is clearly that $w_{j+1}$ is $w_j$ plus $a_j$ (red point added) and minus $v+1$ (all elements are shifted by $1$), i.e. $a_j-(v+1)=w_{j+1}-w_j$. Thus, when $n>m\ge N$: $$\sum_{j=m+1}^n(a_j-(v+1))=w_{n+1}-w_{m+1}\,.$$To finish, it remains to note that the weight ranges from $1+2+\dots+v$ to $(T-v+1)+(T-v+2)+\dots+T$, so its swing is:$$\sum_{i=1}^v (T-v+i) - \sum_{i=1}^v i=\sum_{i=1}^v (T-v)=(T-v)\,v\;. \quad \blacksquare$$

Wow Bandera, finally a clear, concise proof of this! Great solution

http://codeforces.com/blog/entry/19326

Define a function $f: \mathbb{Z}^+ \mapsto{Z}^+$ such that $f(i) = a_i + i$ for all $i$. Note that the function $f$ is injective. Now the problem reads IMO 2015 P6, restated wrote: Let $f: \mathbb{Z}^+ \mapsto{Z}^+$ be an injective function such that for all $i$, we have $i+1 \leq f(i) \leq i+2015$. Prove that there exist two positive integers $b$ and $N$ for which $ \left\vert\sum_{j=m+1}^n(f(j) - j -b)\right\vert\le1007^2 $ for all integers $m$ and $n$ such that $n>m\ge N$ Lemma-1 There are atmost $5000$ integers which are not in the image of $f$

Since the set of integers not in the image of $f$ is finite, pick a large $M$ such that $\mathbb{Z}_{\geq M} \subset Im(f)$, where $Im(f) = \{ f(i) : i \in \mathbb{Z}^+ \}$ Define $f^0(i) = i$, and for $k \geq 0$, $f^{k+1}(i) = f(f^k(i))$ for all $i$. Define an equivalence relation on $\mathbb{Z}_{\geq M}$ such that for any $i,j \in \mathbb{Z}_{\geq M}$, we have $i \sim j$ iff there exist a $k \geq 0$ such that either $i = f^k(j)$ or $j = f^k(i)$. It's easy to see that it's indeed an equivalence relation, so it partitions the integers into some equivalence classes, i.e $\mathbb{Z}_{\geq M} = C_1 \cup \cdots C_k$ with $C_i \cap C_j = \{ \}$ if $i \neq j$, and $i \sim j$ iff there is an $1 \leq l \leq k$ such that $i,j \in C_l$. Lemma-2 $k \leq 2015$

I claim that letting $N = M$ and $b = k$ would work fine. Thorough the rest of the solution, let $m > n \geq M$ be arbitrary positive integers. If $k = 1$, then it's clear $f(i) = i$ for all $i > M$ - for which my claim is trivially true, so assume $k \geq 2$. Define functions $g_1, \cdots, g_k: \mathbb{Z}_{\geq M} \mapsto \mathbb{Z}$ such that $g_i(m)$ is the smallest integer strictly greater than $m$ which is an element of $C_i$. Define $h: \mathbb{Z}_{\geq M} \mapsto \mathbb{Z}$ such that $h(p) = \sum_{1 \leq j \leq k} (g_j(p) - p)$. Lemma-3: $\sum_{n \leq i \leq m} (f(i)-i-k) = h(m) - h(n)$

Lemma-4 $ \frac{k(k+1)}{2} = 1 + \cdots + k \leq h(n) \leq 2015 + (2015-1) + \cdots + (2015 - (k-2) ) + 1 = 2015k - 2014 - \frac{(k-2)(k-1)}{2} $

Note that by taking derivatives, the maximum of $2016x - 2015 - x^2$ is equal to $1007^2$ (call this statement $\spadesuit$). Now, we have $$ \left\vert\sum_{j=m+1}^n(f(j) - j -k)\right\vert \overset{\text{Lemma 3}}{=} |h(m) - h(n)| \overset{\text{Lemma 4}}{\leq} 2015k - 2014 - \frac{(k-2)(k-1)}{2} - \frac{k(k+1)}{2} = 2016k - 2015 - k^2 \overset{\spadesuit}{\leq} 1007^2$$, as desired.

Since $k+a_k$ is injective, it's reasonable to look closer to the sequence $y(n) := n+a_n\,,\,n=1,2,\dots$. We know: 1) $y(n)$ is injective. 2) $1\le y(n)-n\le 2015$. A proper question: how can we construct a sequence of naturals $y(n)$ satisfying 1) and 2)? Instead of trying to establish a mapping $n\to y$, let's try to consider the opposite mapping $y\to n$, that's $n=n(y)$. It may not be defined for all $y\in \mathbb{N}$, but it's a bijection of its domain to $\mathbb{N}$. It also satisfies: $$y-2015 \le n(y)\leq y-1.$$Now, the process of constructing $n(y)$ goes like that: We slide a $1\times 2015$ table (rectangle) along the abscisse axe, where $n$'s lie. At each step we do two things. a) Either mark a number within the rectangle, or do nothing. b) Slide the rectangle one step to the right. We repeat it many times watching that no number escapes unmarked from the rectangle. Marking a number $n$ is interpret as mapping $y\to n $. If we miss it at some step, it means that no $n$ is assigned to that $y$. Note that if we do not mark a number at some step, then the number of unmarked numbers within the rectangle increases. If we mark a number, then the number of unmarked numbers within the rectangle remains unchanged. So, there are only finitely many times we can miss marking a number. It means, after some place on, we mark a number at every step. In other words, if we go back to mapping $n\to y(n)$, it is bijection, from some $n$ on. Thus, if we sort in increasing order $y(n)$ for sufficiently large $n$, we will get a function $y^*(n)=n+b$. That $b$ is exactly what we seek for. In that rearrangement, $y(n)$ can be moved no more than $2015$ positions from its original place. Using it, it remains to apply some standard arguments. Comment: That was the way I saw it and it came to me in a natural way. That's why I decided to share it, despite there is nothing new in the core of that idea.

Pretty much the same as oneplusone's solution. Just using this to practice writing-up. Consider the set $T = \{k+a_k\mid k\in\mathbb{Z}^+\}$. We note the following trivial observation. Claim: The cardinality of the set $B = \mathbb{Z}^+\setminus T$ is at most $2015$. Proof: For any large $M$, sequence $1+a_1, 2+a_2,\hdots, M+a_M$ omits at most $2015$ integers in $\{1,2,\hdots,M+2015\}$. Taking $M$ large yields the desired result. $\blacksquare$ Now we state the magical observation, which clearly implies the problem. Main Claim: Taking $b = |B|$ and $N > \max B$ works. Proving this is a straightforward bounding (the hard part is finding it). Define $s_n = a_1+a_2+\hdots + a_n$ and let $c = \sum_{x\in B} x$. We claim that Claim: For any integer $n > N$, $$\frac{b(b+1)}{2} \leq s_n - bn + c \leq \frac{b(4033-b)}{2}-2015$$Proof: Consider $S_n = \{1+a_1, 2+a_2,\hdots, n+a_n\}$. It contains all integer in $\{1,2,\hdots,n+2015\}$ except the following Each element of $B$. Another $2015-b$ integer which appears in $k+a_k$ for $k>n$. These integers are in $\{n+2, n+3,\hdots, n+2015\}$ This gives the following estimate. \begin{align*} \sum_{k=1}^n (k+a_k) &\geq [1+2+\hdots +(n+2015)] - c - [(n+b+1)+(n+b+2)+\hdots + (n+2015)] \\ &= \frac{n(n+1)}{2} - c + bn + \frac{b(b+1)}{2} \end{align*}and \begin{align*} \sum_{k=1}^n (k+a_k) &\leq [1+2+\hdots +(n+2015)] - c - [(n+2)+(n+3)+\hdots + (n+b+1)]\\ &= \frac{n(n+1)}{2} - c + bn + \frac{4033b-b^2-4030}{2} \end{align*}after some bloody computation. $\blacksquare$ Finally, we have \begin{align*} \left\lvert\sum_{j=m+1}^n (a_j-b)\right\rvert &= |(s_n-bn)-(s_m-bm)| \\ &\leq \left(\frac{b(4033-b)}{2}-2015\right) - \frac{b(b+1)}{2} \\ &= b(2016-b)-2015 \\ &\leq 1008^2-2015 \end{align*}which is equal to $1007^2$ as desired.

Claim 1: The sequence $i+a_i$ is eventually surjective. That is, it is cofinite over the naturals. Proof: Consider the directed graph on the natural numbers, where we draw $i\to j$ if $a_i-1=j-i$. Note that every vertex has outdegree $1$, and if we have both $i\to j$ and $i'\to j$, then $a_i+i=a_{i'}+i'=j+1$, which is a contradiction. So, all vertices also have indegree at most 1, and our directed graph must be composed of cycles and chains. Now, note that for each chain, if $i,j$ are consecutive elements, $j-i=a_i-1\le 2014$, so the density of each sequence is at least $\frac{1}{2014}$. Hence, we can have at most $2014$ chains, and there exists $N$ such that no chains start at index $x>N$. Then, beyond $N$, all vertices have in-degree exactly $1$. As an in-edge to $j$ means that $\exists i$ with $a_i+i=j+1$, we have that $i+a_i$ is surjective over $\mathbb{N}_{>N+1}$ as desired. Now, for each consecutive block of integers $[m,n]$ with $n-m\ge 2014$, we define its leakiness to be $$\left\arrowvert \{m< x<m+2015\}\cap\{a_i+i|m\le i\le n\}\right\arrowvert$$For convenience, denote the second set as $S(m,n)$. Note that for each $[m,n]$ with $n-m\ge 2014$, $S(m,n)$ must completely cover $[m+2015,n+1]$, since only numbers in this range can reach them, and we have to have $\{a_i+i\}$ is surjective. So, we also have that leakiness is $2014-\left|S(m,n)\cap\mathbb{N}_{>n+1}\right|$. The second term we denote as coleakiness. Claim 2: All $(m,n]$ with $n-m\ge 2014$ and big $m,n$ have the same leakiness. Proof: First, consider $[m,n]$ and $[n+1,2n-m+1]$. Note that $S(m,2n-m)$ completely covers $[n+2,n+2015]$. However, this set must be covered exactly by the elements corresponding to the leakiness of $[n+1,2n-m+1]$ and the coleakiness of $[m,n]$. And, as these two values add to the size of the interval, or $2014$, we have that $[m,n]$ and $[n+1,2n-m+1]$ have the same leakiness. Now, suppose that we have two intervals $[m,n]$ and $[m^*,n^*]$. First, we use the above to shift $[m^*,n^*]$ to $[m',n']$ such that $m'>n+65537$, and the two intervals have the same leakiness. Then, consider $[n+1,m'-1]$. $S(n+1,m'-1)$ must cover everything in $[n+2,m'+2014]$ which $S(m,n)$, $S(m',n')$ do not, since $\{a_i+i\}$ is surjective. However, since it has $m'-n-1$ elements and this interval has $m'-n+2013$, we must have that $S(m,n)$ and $S(m',n')$ cover exactly $2014$ elements in this range. However, the only elements of $S(m,n)$ and $S(m',n')$ within this range are those corresponding to their coleakiness and leakiness respectively. So, like before, we get that $[m,n]$ and $[m',n']$ have the same leakiness, which means that $[m,n]$, $[m^*,n^*]$ have the same leakiness, as desired. As we have that all intervals with size at least $2015$ have the same leakiness, we will denote this common leakiness as $L$. Claim 3: $b=2015-L$ satisfies the problem statement. Proof: First assume that $n-m\ge 2014$. We first compute $\sum_{i=m}^n a_i+i=\sum_{k\in S(m,n)}k$. Recall that $S(m,n)$ must include $[m+2015,n+1]$. For the remaining elements, we have that $L$ of them are of the form $m+c$, and $2014-L$ of them have the form $n+1+c$, where $1\le c\le 2014$. So, $$\sum_{k\in S(m,n)}k=\frac{(m+n+2016)(n-m-2013)}{2}+Lm+(2014-L)(n+1)+C$$where we can bound $C\in\left[2\cdot\frac{1007\cdot 1008}{2},2\cdot\frac{1007\cdot 3022}{2}\right]$. Then, we have $$\sum_{i=m}^n a_i=(Lm+(2014-L)(n+1)+C)+\frac{(m+n+2016)(n-m-2013)}{2}-\frac{(m+n)(n-m+1)}{2}$$$$=(2015-L)(n+1-m)+C-1007\cdot 2015$$So, if we set $b=2015-L$, the sum becomes $$\bigg|\sum_{i=m}^n (a_i-b)\bigg|=|C-1007\cdot 2015|$$Using our earlier bounds for $C$, we see that the RHS is at most $3022\cdot1007-2015\cdot 1007=1007^2$, as desired. Thus, it remains to see that $2015-L$ also works for smaller intervals. However, for a small interval $[m,n]$, we can consider subtracting the sums $[a,n]$ and $[a,m)$, where $a$ is chosen such that both of these intervals are sufficiently large. Then, we will get that $\left|\sum_{i=m}^n(a_i-b)\right|=\left|C_{[a,n]}-C_{[a,m)}\right|$. These two values of $C$ have the same contribution from the left sides of the intervals (i.e. sum of $c$ over $a+c$) since they share the same lower bound, so the maximum difference between them is actually $$(2014+2016+\ldots+(L+1))-(1+2+\ldots+(2014-L))\le 1007\cdot 1511-1007\cdot 504=1007^2$$So, as we have proven the question over all cases, we are done.

Line up $\mathbb N$ in ascending order and in step $i$, if there are no grasshoppers on $i$, put a grasshopper on number $i$ and have it jump to $i+a_i$; otherwise simply have the grasshopper on $i$ jump onto $i+a_i$. The grasshoppers always make jumps of sizes between $1$ and $2015$ and no number will be jumped on by two different grasshoppers, hence we can put at most $2015$ grasshoppers. This also means that eventually the jumps of the $c \le 2015$ grasshoppers will cover all numbers (otherwise we can add another grasshopper, contradiction). Note that $\sum_{i=m+1}^n a_i$ is the sum of lengths of jumps at $m+1,\dots,n$. Let $m+k_1,\dots,m+k_c$ be the leftmost positions jumped on by grasshoppers $1,\dots,c$ that are $> m$, and $n+l_1,\dots,n+l_c$ the leftmost positions jumped by grasshoppers $1,\dots c$ that are $> n$. The total sum of jump lengths is $\sum_{i=1}^c \left((n+l_i) - (m+k_i)\right) = c(n-m) + \sum_{i=1}^c (l_i - k_i)$. Now note that no grasshopper can miss $2015$ consecutive numbers, hence $k_1,\dots, k_c,l_1,\dots,l_c$ are all $\in [1,2015]$, so we may choose $b = c$ in the problem and we are done.

Solved with eisirrational, goodbear. For each positive integer \(i\), draw an arrow from \(i\) to \(i+a_i\) on the number line. This partitions the positive integers into several chains. Observe that among any 2015 consecutive integers, each chain must contain at least one number. In particular, the number of chains is finite. Say a chain has been introduced if its first element has appeared in the sequence. I claim we can set \(b\) equal to the number of chains, and \(N\) the first integer for which all chains have already been introduced. Fix \(m\) and \(n\), and number the chains 1, \ldots, \(b\). For each \(i\), let \(d_k(i)\) be the least positive integer \(j\) such that \(a_{i+j}\) is in the \(k\)th chain. Furthermore, let \[S(i)=d_1(i)+d_2(i)+\cdots+d_b(i).\]Observe that \(a_j-b=S(j)-S(j-1)\), so \[\sum_{j=m+1}^n\big(a_j-b\big)=S(n)-S(m).\] Now we can easily establish \[1+2+\cdots+b\le S(i)\le1+\underbrace{2015+2014+\cdots}_{b-1\text{ terms}}.\]Hence \(|S(n)-S(m)|\le(b-1)(2015-b)\le1007^2\), as needed. Remark: This is really a juggling problem: a ball launched at time \(i\) his airtime \(a_i\) and returns at \(i+a_i\). Here, \(b\) is the number of balls and \(N\) is the first time when all the balls have been launched.

As in many of the solutions above, interpret the situation as a juggling problem: we throw a ball in the air at time $t$ with our left hand and catch it with out right hand at time $t + a_t$. Lemma 1. The number of balls in the air is non-decreasing with respect to time and bounded by $2015$. Proof: Since we throw a ball in the air at each second and at each second we catch at most one ball, the number of balls in the air is non-decreasing. Furthermore, it is bounded by $2015$, as there cannot be two balls which have the same time left before being catched and these times are positive integers bounded by $2015$. Hence there is some $b$ such that after sufficiently long time has passed, the number of balls in the air is a constant $b$. We claim that this $b$ is what we want. At time $t$, let $H(t)$ be the sum of the quantities "time left before this ball is catched" over all balls currently in air. The main claim is that \begin{align*} H(t+1) = H(t) - b + a_{t+1}. \end{align*}Indeed: when one time unit passes, each of the $b$ balls are one time unit closer to being catched (resulting in the $-b$ above) and we throw a new ball such that it is catched in $a_{t+1}$ time units from now. Hence, the sum in the problem statement is a telescopic sum: \begin{align*} \Big|\sum_{j = m+1}^n a_j - b \Big| = \Big|H(n) - H(m)\Big|. \end{align*}We are left with proving that the minimum and maximum values of $H$ are not too far away from each other. The minimum value is attained when the balls have times $1, 2, \ldots , b$ left before being catched. This gives $H(t)$ equal to $b(b+1)/2$. The maximum value is attained when the balls have times $2015, 2014, \ldots , 2015 - (b-2), 1$ left before being catched. (Note that since the number of balls $b$ in the air is constant, we have to catch one ball each second, so we need to have one ball with one time unit left before being catched.) This gives $H(t)$ equal to $(b-1)(4030 - (b-2))/2 + 1$. The difference between the maximum and minimum values is \begin{align*} \frac{4032b - b^2 - 4030 + b}{2} - \frac{b^2 + b}{2} = \frac{4032b - 4034 - 2b^2}{2} = b(2016 - b) - 2015 \le 1008^2 - 2015 = 1007^2. \end{align*}

Slight hints used

Now, I claim that letting $b$ equal the number of chains and $N$ be the largest "first integer" of the chain (i.e. the largest $k$ such that there doesn't exist $a$ with $f(a)=k$) works. For a chain $C$ and integer $x \geq N$, let $M(C,x)$ denote the least element of $C$ that's greater than $x$. One can see that for $n>m \geq N$, we have $$\sum_{j=m+1}^n a_j=\sum_{C \text{ chain}} (M(C,n)-M(C,m))=\sum_{C \text{ chain}} M(C,n)-\sum_{C \text{ chain}} M(C,m).$$Evidently we have $$\sum_{C \text{ chain}} M(C,n) \geq (n+1)+(n+2)+(n+3)+\cdots+(n+b)=bn+(1+2+3+\cdots+b).$$Further, since $M(C,n)=n+1$ for some $C$, we have $$\sum_{C \text{ chain}} M(C,n) \leq (n+1)+(n+2017-b)+(n+2018-b)+\cdots+(n+2015)=bn+(1+(2017-b)+(2018-b)+\cdots+2015).$$Likewise, we have $$bm+(1+2+\cdots+b) \leq \sum_{C \text{ chain}} M(C,m) \leq bm+(1+(2017-b)+(2018-b)+\cdots+2015).$$It follows that $$b(n-m)-(b-1)(2015-b) \leq \sum_{C \text{ chain}} M(C,n)-\sum_{C \text{ chain}} M(C,m) \leq b(n-m)+(b-1)(2015-b),$$so $$\left \lvert \sum_{j=m+1}^n (a_j-b)\right \rvert \leq (b-1)(2015-b) \leq 1007^2.~\blacksquare$$

One of the easiest IMO 6's ever IMO (:p). Define the injective function $f(j)=j+a_j$. Since for any positive integer $N$, $\{f(i)|1\le i\le N\}$ consists of $N$ integers between $2$ and $N+2015$, there are at most $2015$ naturals not in the range of $f$. Now, draw an infinite directed graph with edges $x\rightarrow f(x)$ for all $x\in \mathbb{N}$. Each vertex in $f(\mathbb{N})$ has outdegree $1$ and indegree $1$, so $f$ consists of some $1\le c\le 2015$ chains. I claim that taking $b=c$ and $N>\sup(\mathbb{N}\setminus f(\mathbb{N}))$ works. For each chain $C_1, C_2\ldots C_k$ containing at least value in $[m+1,n]$, let $M_i$ be the maximum of $C_i\cap [m+1,n]$ and $m_i$ be the minimum. It's not hard to see that the sum $\sum_{j=m+1}^n f(j)-j-c=\sum_{j=m+1}^n a_j-b$ is equal to $S_{m,n}=\left[\sum_{i=1}^k f(M_i)-m_i \right]-c\cdot (n-m)$. Consider the two terms in the sum independently; the maximum value of $\sum f(M_i)$ is $1+2015+2014+\ldots +(2017-k)+kn$, while its minimum is $1+2+\ldots +k+kn$. Similarly, the minimum value of $\sum m_i$ is $1+2+\ldots +k+km$, while its maximum is $1+2015+2014+\ldots +(2017-k)+km$. In case $k=c$, we have the result by taking extreme cases; indeed, $|S|$ is at most $(c-1)(2015-c)$ after simple arithmetic. When $k<c$, notice that $S_{m,n}=S_{m,n+2015}-S_{n,n+2015}$; it's easy to see that both intervals on RHS contain all chains, when the RHS is expanded, the two identical instances of the term $\sum f(M_i)$ cancel out, so the absolute value of RHS is at most $(c-1)(2015-c)$ too as desired.

Very nice and very intuitive problem. The idea is to set $f(k) = k+a_k$ and notice that the graph of $f$ is composed of disjoint infinite directed paths by injectivity. Let $b$ be the number of such paths, and label them $P_1, P_2, \dots, P_b$. Let $a_i$ be the minimum element in $P_i$ greater than $n$ and $b_i$ to be the maximum element less than $m$. Claim. We have exactly $$\sum_{j=m+1}^n (a_j - b) = \sum_{i=1}^b (a_i-b_i -n+m).$$ Proof. Notice that the sum of $a_i-b_i$ in one cycle represents the sum of all $a_j$ in the cycle such that $j \in [a_i, b_i]$, which represents all the valid terms in the sequence in the cycle. $\blacksquare$ So now \begin{align*} \sum_{j=m+1}^n (a_j - b) &= \sum_{i=1}^b (a_i - n) - \sum_{i=1}^b (b_i - m) \\ &\geq 1+2015+2014+\cdots+2015-(b-2) - (1+2+\cdots+b) \\ &=(b-1)(2015-b) \leq 1007^2. \end{align*}The other direction is analogous.

Consider the following graphical representation: on the positive integer number line, we draw a directed edge from $n$ to $n+a_n$ for all positive integers $n$. Note that each positive integer has outdegree one and indegree at most one. Although this is a graph, each edge shall retain spacial information: in particular, its length, which is $a_n$ and thus must be between $1$ and $2015$ inclusive. $~$ This graph is composed of a number of disjoint paths leading right on the number line. Let there be $b$ paths. This number is finite and at most $2015$ because each path must go through have a vertex in any interval $[k+1,k+2015]$. Let $N$ be at a point where no new paths are starting. For all the edges of this graph that begin in $[m+1,n]$, we color it red. Note that \[\sum_{j=m+1}^n(a_j)\]is simply the sum of lengths of all the edges that begin in $[m+1,n]$ so it is the sum of lengths all red edges. We count this path-wise. This is simply the sum of the distance between the smallest numbers at least $n+1$ and at least $m+1$. The rest is calculation that I don't particularly want to do.

We go to the real line and correspond it to the integers $a_i$. To each positive integer $i$ correspond the closed interval $D_i=[i+a_i-2015,i+a_i-1]$, which has integer ends, contains $i$, and has a length of $2014$. Condition 2 gives us $D_i \neq D_j$. Next, we observe that positive integers that are not the left end of some interval are finite since otherwise, we would have that the left end of some $D_i$ is greater than $i$. So there is $N$ such that for every $i \geq N$, $i$ is the left end of some interval. Now from $i \geq N$, exactly $k<2015$ of them give intervals with a right edge less than $N$. Induction on $N$ follows that for every $N'>N$, exactly $k$ integers greater than or equal to $N'$ give intervals with a left edge less than $N'$. Now, let's say we choose $n>m\geq N$. For each $i,j$ contained in the interval of the other, we can exchange their intervals, and the sum of their numbers remains constant. By applying this operation, we can get, for each $i>j \geq N$, its $D_i$ left edge to be to the right of its left edge $D_j$. Then the first $k$ integers after $m$ will have a left edge at most $m$, and all other numbers $i$ between $m$ and $n$ will have a left edge of $i-k$. Let $b=2015-k$. Prime $k$ numbers contribute to the sum an integer between $-k(2014-k)$ and $0$, with $-1007^2 \leq -k(2014-k) \leq 0$. The remaining integers of space contribute to $0$ the sum. But some of their intervals may have originally belonged to numbers greater than $n$. Because the intervals we used have a left edge less than $n-k$, at most $2014-k$ of them can be derived from an integer greater than $n$. To find its space to the right of $n-k$, each of these $2014-k$ integers must have originally had a number greater than or equal to $2015-k$. So these numbers contribute to the sum a number between $0$ and $(2014-k)k \leq 1007^2$. So the sum lies between $-1007^2$ and $1007^2$.

this solution is essentially equivalent to the juggling solution after reading that, but I think its way more natural to come up with it, especially after having solved 2012 A6 (which I believe is more C than this is A). Even though it's way more annoying to write up (better if you can use pictures but I am not proficient enough in LaTeX for that) I think it's still very elegant in it's essence. Anyway. For each member of the sequence $a_i$ we assign a point $P(i,a_i)$ in the euclidian plane. now to each such point assign the line $l_i$ of slope $-1$ that passes through said point. It's clear that the condition of the problem now translates into the following: consider the sequence of points, and the set of all lines passing through the integer lattice, then each line has at most one point lying on it. Now, consider $2015 \times2015$ rectangles (yes ok they are squares but they are also rectangles so leave me alone) such that no points are above and below the rectangles (we will later show that it doesn't matter in which way we choose this rectangle) and all of them are after each other (basically we split the points into groups of $2015$). For a given rectangle, there are $4029$ lines passing through it, we call those "left-leaning" that intersect the left edge of the rectangle, and "right-leaning" those intersecting the right edge. Now there is the one in the middle which we will just assign to be right-leaning. Within the rectangle, colour all points lying on right-leaning lines red, and the others blue. This was all just setup We claim that as we go from rectangle to rectangle, the number of points in our sequence that are red is increasing. Indeed, this is not hard to see now, every right-leaning line (apart from the middle one, but that is compensated by there being less left-leaning lines than right-leaning ones) in one is also a left-leaning line in the next, which is therefore blocked. Now since the amount of red points in our sequence is increasing, we can now take it's limiting value, and call that value $m$. We now can quickly show that the value of $m$ doesn't change of we shift over out initial selection of rectangles by one point, aka where we start doesn't matter, for that note that the red region loses a point at the left and gains one at the right (or vice versa) so we are fine. Now what we want $b$ to be is a quantifier of how high on average our members of the sequence are, and $m$ seems like a beautiful choice, since intuitively, the red points are higher than the blue ones, so let's set $b=m$ and try to prove that. For that we now need to interpret what our given sum means: considering a vertical strip in the plane (since $m$ doesn't change how we select our rectangles, we can without loss of generality assume this vertical strip to be at the end of such a rectangle) is the sum of the last $m$ members of our sequence, each having their height decreased by $s$ if they appeared $s$ steps ago (basically we sum up the heights of the intersects of all lines with points on them passing through our vertical strip), considering the difference of two consecutive strips, this is exactly $a_{n+1}-m$ This let's us perfectly interpret our summation, it's now simply the difference between the sum of intercepts between two strips. Bounding this by $1007^2$ is easy (just take the obvious bounds), so we are done

We interpret this as a directed graph where we link $n$ with $n+a_n$, thus from condition two we get that this directed graph is a number of infinite paths. Thus let $b$ be the maximal number of distinct paths and let $N$ be the last value where a new path starts. We know we have at most $2015$ paths from the size condition so we know $N$ exists. Thus we get that for any segment $m+1$ to $n$, that the sum of the values $a_{m+1}$ to $a_{n}$ is the sum of the lengths of the $b$ paths. So we get that this length at maximum is $b(n+1-m+2015-b)$ and at minimum is $(n-m-1)+b+(b-1)(n-m-2017+b)$ and we find when we subtract $(n-m-1)b$ from both of those the absolute value is less than $1007^2$.

Very nice one. Firstly, let $f(k)=a_k+k$ we are given that $f$ is injective. Note that there are no cycles in graph of $f$, and it’s made of disjoint infinite chains. Claim : There are at most $2015$ chains. This is the same idea used in 2012 A6, assume at some point all elements of the chains are less than $N$, and assume that after one step they will be more or equal to $N$, then since $a_i \leq 2015$ for all $i$, then the elements will be the interval $[N,N+2015)$ but as they are distinct elements, and there are $2015$ values in the interval, hence there are at most $2015$ chains.$\blacksquare$ Now let our chains be $C_1,C_2,….,C_k$, we claim that $k=b$, in other words the number of chains is our desired $b$. So we first want to change the sum \[\sum_{j=m+1}^n(a_j)\] Into something related to our chains, so let $m(C_i,n)$ denote the minimum element of chain $C_i$ more than or equal $n$, then we have that. \[\sum_{j=m+1}^n(a_j)=\sum_{chains} (m(C_i,n)) - (m(C_i,m))\] And so \[\sum_{j=m+1}^n(a_j-b)=\sum_{chains} (m(C_i,n)-n) - (m(C_i,m)-m)\] After some calculation we get that \[\sum_{j=m+1}^n(a_j-b) \leq (b-1)(2015-b) \leq 1007^2\] Similarly for bound from below. And we are done

This is an Example problem from OTIS and I was following walkthrough so solution unlikely to be incorrect.