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 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.