Difference between revisions of "2015 IMO Problems/Problem 6"
(Bandera's solution --- Greetings from Ukraine!) |
m (Problem statement added) |
||
Line 1: | Line 1: | ||
− | + | ==Problem== | |
+ | The sequence <math>a_1,a_2,\dots</math> of integers satisfies the conditions:<br /><br /> | ||
+ | (i) <math>1\le a_j\le2015</math> for all <math>j\ge1</math>,<br /> | ||
+ | (ii) <math>k+a_k\neq \ell+a_\ell</math> for all <math>1\le k<\ell</math>.<br /><br /> | ||
+ | Prove that there exist two positive integers <math>b</math> and <math>N</math> for which<cmath>\left\vert\sum_{j=m+1}^n(a_j-b)\right\vert\le1007^2</cmath>for all integers <math>m</math> and <math>n</math> such that <math>n>m\ge N</math>.<br /><br /> | ||
+ | Proposed by Ivan Guo and Ross Atkins, Australia | ||
+ | |||
+ | ==Solution== | ||
+ | |||
+ | We can prove the more general statement.<br /><br /> | ||
<u>'''Theorem'''</u> ''Let <math>T</math> be a non-negative integer parameter. If given a sequence <math>a_1,a_2,\dots</math> that satisfies the conditions:''<br /> | <u>'''Theorem'''</u> ''Let <math>T</math> be a non-negative integer parameter. If given a sequence <math>a_1,a_2,\dots</math> that satisfies the conditions:''<br /> | ||
(i) <math>1 \le a_j \le T+1</math> ''for all'' <math>j \le 1;</math><br /> | (i) <math>1 \le a_j \le T+1</math> ''for all'' <math>j \le 1;</math><br /> | ||
Line 9: | Line 18: | ||
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 <math>x</math>). Call it the point's ''trace'' and paint black. Finally, the set <math>P_x=\{\,y \mid (x,y) \text { is black}\}</math> will be called a ''pattern'', the number elements <math>|P_x|</math> in it will be called its ''volume'' and the sum <math>w_x</math> of all elements in <math>P_x</math> will be called its ''weight''.<br /> | 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 <math>x</math>). Call it the point's ''trace'' and paint black. Finally, the set <math>P_x=\{\,y \mid (x,y) \text { is black}\}</math> will be called a ''pattern'', the number elements <math>|P_x|</math> in it will be called its ''volume'' and the sum <math>w_x</math> of all elements in <math>P_x</math> will be called its ''weight''.<br /> | ||
Now let <math>j>N</math>. Lets track how <math>P_j</math>, its volume and its weight change when <math>j</math> increases by 1. Obviously <math>P_{j+1}</math> is <math>P_j</math> plus added <math>a_j</math> (red point) and shifted down by <math>1</math>; a point that goes to <math>0</math> vanishes. This means that the volume doesn't change at all. Indeed, if <math>1 \notin P_j</math>, then <math>a_j=1</math> or the carrier <math>L_{j+1}</math> will remain unoccupied, so one point always vanishes going to <math>0</math>, and exactly one point is added before the shift (it may be the same point). Let <math>v</math> be this constant volume. As a pattern never contains <math>T+1</math>, <math>v</math> ranges from <math>0</math> to <math>T</math>. Now it is clearly that <math>w_{j+1}</math> is <math>w_j</math> plus <math>a_j</math> (red point added) and minus <math>v+1</math> (all elements are shifted by <math>1</math>), i.e. <math>a_j-(v+1)=w_{j+1}-w_j</math>. Thus, when <math>n>m\ge N</math>: <cmath>\sum_{j=m+1}^n(a_j-(v+1))=w_{n+1}-w_{m+1}\,.</cmath>To finish, it remains to note that the weight ranges from <math>1+2+\dots+v</math> to <math>(T-v+1)+(T-v+2)+\dots+T</math>, so its swing is:<cmath>\sum_{i=1}^v (T-v+i) - \sum_{i=1}^v i=\sum_{i=1}^v (T-v)=(T-v)\,v\;. \quad \blacksquare</cmath> | Now let <math>j>N</math>. Lets track how <math>P_j</math>, its volume and its weight change when <math>j</math> increases by 1. Obviously <math>P_{j+1}</math> is <math>P_j</math> plus added <math>a_j</math> (red point) and shifted down by <math>1</math>; a point that goes to <math>0</math> vanishes. This means that the volume doesn't change at all. Indeed, if <math>1 \notin P_j</math>, then <math>a_j=1</math> or the carrier <math>L_{j+1}</math> will remain unoccupied, so one point always vanishes going to <math>0</math>, and exactly one point is added before the shift (it may be the same point). Let <math>v</math> be this constant volume. As a pattern never contains <math>T+1</math>, <math>v</math> ranges from <math>0</math> to <math>T</math>. Now it is clearly that <math>w_{j+1}</math> is <math>w_j</math> plus <math>a_j</math> (red point added) and minus <math>v+1</math> (all elements are shifted by <math>1</math>), i.e. <math>a_j-(v+1)=w_{j+1}-w_j</math>. Thus, when <math>n>m\ge N</math>: <cmath>\sum_{j=m+1}^n(a_j-(v+1))=w_{n+1}-w_{m+1}\,.</cmath>To finish, it remains to note that the weight ranges from <math>1+2+\dots+v</math> to <math>(T-v+1)+(T-v+2)+\dots+T</math>, so its swing is:<cmath>\sum_{i=1}^v (T-v+i) - \sum_{i=1}^v i=\sum_{i=1}^v (T-v)=(T-v)\,v\;. \quad \blacksquare</cmath> | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | {{IMO box|year=2015|num-b=5|num-a=6}} | ||
+ | |||
+ | [[Category:Olympiad Combinatorics Problems]] |
Revision as of 23:39, 5 October 2015
Problem
The sequence of integers satisfies the conditions:
(i) for all
,
(ii) for all
.
Prove that there exist two positive integers and
for which
for all integers
and
such that
.
Proposed by Ivan Guo and Ross Atkins, Australia
Solution
We can prove the more general statement.
Theorem Let be a non-negative integer parameter. If given a sequence
that satisfies the conditions:
(i) for all
(ii) for all
then there exist two integers and
,
and
, for which
for all integers
and
such that
.
Proof Consider the set of points on a plane: (let's call it the base strip). The sequence is represented on it by the subset
which is painted red. Each line
of kind
, where
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 with
, where
, cover the part of the base strip having
, so there are at least
red points lying on them. Thus, the number of free carriers among them is at most
. Since
is arbitrary, the total number of free cariers doesn't exceed
. Take
such that all the carriers
with
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 ). Call it the point's trace and paint black. Finally, the set
will be called a pattern, the number elements
in it will be called its volume and the sum
of all elements in
will be called its weight.
Now let . Lets track how
, its volume and its weight change when
increases by 1. Obviously
is
plus added
(red point) and shifted down by
; a point that goes to
vanishes. This means that the volume doesn't change at all. Indeed, if
, then
or the carrier
will remain unoccupied, so one point always vanishes going to
, and exactly one point is added before the shift (it may be the same point). Let
be this constant volume. As a pattern never contains
,
ranges from
to
. Now it is clearly that
is
plus
(red point added) and minus
(all elements are shifted by
), i.e.
. Thus, when
:
To finish, it remains to note that the weight ranges from
to
, so its swing is:
See Also
2015 IMO (Problems) • Resources | ||
Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
All IMO Problems and Solutions |