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.