2009 IMO Problems/Problem 6
Contents
Problem
Let be distinct positive integers and let be a set of positive integers not containing . A grasshopper is to jump along the real axis, starting at the point and making jumps to the right with lengths in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in .
Author: Dmitry Khramtsov, Russia
Solution 1
We will use strong induction on . When , there are no elements in , so the one jump can be made without landing on a point in . When , we consider two cases. If is not in , then the order will work. If is in , then is not in and the order will work. We will assume that the order can be chosen in such a way for all integers for .
When , we can assume WLOG that . We can also assume that the elements of are distinct, since if two elements are identical, we can treat them as one and use induction on . We now consider four cases:
Case 1: is in but are not.
There are at most elements in greater than . Then, from our assumption, there exists an order of jumps starting from of lengths where the first jump is such that the grasshopper will not land in any point in . We can then switch the jumps and . Since is not in and no subsequent jumps result in the grasshopper landing in a point in , this sequence is valid.
Case 2: is not in but at least one of is.
There are at most elements in greater than . Then, from our assumption, there exists an order of jumps starting from of lengths such that the grasshopper will not land in any point in . Adding at the beginning of this sequence then results in a valid sequence.
Case 3: is in and at least one of is.
Consider the following pairs of distinct integers . Since at most of these points are in , by the pigeonhole principle, there exists an integer such that are both not in . Since there are at most elements greater than , at most elements are greater than . Then, from our assumption, there exists an order of jumps starting from of lengths such that the grasshopper will not land in any point in . Adding at the beginning of this sequence then results in a valid sequence.
Case 4: None of are in .
Assume that there exists no valid sequence - that any order of jumps will result in the grasshopper landing on at least one element in . We can select any element in and, from our assumption, construct a sequence beginning at some containing jumps that will not land on any of the other elements in . Since no valid sequence exists, during this sequence of jumps, the grasshopper must land on .
WLOG, we let . We let and and use the corresponding sequence that only lands on and no other element in . Let the jump immediately after landing on be , where . We swap jumps and . Now, since , all jumps before will land on a integer less than . Since is the smallest element in , none of the jumps before will land on a point in . Since no jumps after will land on an element in by the construction, the grasshopper must then land on an element in after making the jump . However, this would imply that the original construction would land on another element different from , but this is a contradiction. So, a valid sequence must exist.
Since we have an induction on , the statement must be true for all , and we are done.
Solution 2
This solution will use induction rather than strong induction; as a result, it will be less rigorous.
We proceed as the above step to prove that the grasshopper succeeds for and . We now assume that the grasshopper succeeds for , and we are to prove that it still succeeds for . Let us call the grasshopper's "trajectory" as the path it takes with elements to never land on a point in . We are now going to add the grasshopper can make and another point to to prove that the grasshopper wins for . There are 4 cases for where this last point to could be. We will denote this point as .
Case 1: is not along the trajectory of the grasshopper. In this case, the grasshopper can make the jump of after completing its trajectory, since it will not land on . Since cannot be equal to , we do not have to worry if the jump lands on .
Case 2: is along the trajectory of the grasshopper. Now, we analyze where along this trajectory is. We will now attempt to prove that it is possible to change the path the grasshopper takes to avoid . Assume is the point the grasshopper reaches after jumps. The worst-case scenario would be that all of the points of block a combination of jumps. Since no point of can be at the origin or be equal to , we have that . The number of combinations of jumps would be , which always exceeds the number of points in , since the smallest value, where , results in combinations, but has only points and thus combinations to prevent.
See Also
1959 IMO (Problems) • Resources | ||
Preceded by Problem 1 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 3 |
All IMO Problems and Solutions |