2015 IMO Problems/Problem 6
Problem
The sequence of integers satisfies the conditions:
(i) for all ,
(ii) for all .
Prove that there exist two positive integers and for whichfor 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 Last question |
All IMO Problems and Solutions |