2009 IMO Problems/Problem 6
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
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.
See Also
2009 IMO (Problems) • Resources | ||
Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Last Problem |
All IMO Problems and Solutions |