Difference between revisions of "2015 IMO Problems/Problem 6"

Latest revision as of 00:33, 31 December 2019

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$

@@ Line 21: / Line 21: @@
 ==See Also==
-{{IMO box|year=2015|num-b=5|num-a=6}}
+{{IMO box|year=2015|num-b=5|after=Last question}}
 [[Category:Olympiad Combinatorics Problems]]

2015 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last question
All IMO Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "2015 IMO Problems/Problem 6"

Latest revision as of 00:33, 31 December 2019

Problem

Solution

See Also