Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2015 IMO Problems/Problem 6

Problem

The sequence $a_1,a_2,\dots$ of integers satisfies the conditions:

(i) $1\le a_j\le2015$ for all $j\ge1$,
(ii) $k+a_k\neq \ell+a_\ell$ for all $1\le k<\ell$.

Prove that there exist two positive integers $b$ and $N$ for which\[\left\vert\sum_{j=m+1}^n(a_j-b)\right\vert\le1007^2\]for all integers $m$ and $n$ such that $n>m\ge N$.

Proposed by Ivan Guo and Ross Atkins, Australia.

Solution

We can prove the more general statement.

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 \le 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 Consider the set of points on a plane: $\{(x,y) \mid x,y \in \mathbb N,\,y \le T+1\}$ (let's 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 we 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$. Lets 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\]

See Also

2015 IMO (Problems) • Resources
Preceded by
Problem 5 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Last question
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2015_IMO_Problems/Problem_6&oldid=113808"