# [Math] The infamous Grasshopper problem

This is one of the hardest problems in IMO history. As regulated by IMO rules, it permits solutions involving only elementary techniques. My solution is very similar to the official one.

## The infamous Grasshopper problem

Let *a*_{1}, *a*_{2}, ... , *a*_{n} be distinct positive integers
and let *M* be a set of *n* − 1 positive integers not containing
*s* = *a*_{1} + *a*_{2} + ... + *a*_{n}. A grasshopper is to jump along the real axis,
starting at the point 0 and making *n* jumps to the right with
lengths *a*_{1}, *a*_{2}, ..., *a*_{n} in some order. Prove that the order can be
chosen in such a way that the grasshopper never lands on any point in *M*.

## Proof

First note that the statement is still equivalent if |*M*| < *n*.

Let the set *M* = {*b*_{1}, *b*_{2}, ..., *b*_{n − 1}}, where
0 < *b*_{1} < *b*_{2} < ... < *b*_{n − 1} < *s*. We will prove by induction on
*n*. *n* = 1 and *n* = 2 are trivial. Suppose the statement
holds for all *n* ≤ *m*. We want to prove that it holds for
*n* = *m* + 1 ≥ 3.

## Lemma

If there's any *a*_{i} > *b*_{1} that doesn't belong to *M*, then we're
done here. This is because placing *a*_{i} at [0, *a*_{i}] covers at
least one point *b*_{1} in *M*, and there are now *n* − 1
segments and less than *n* − 1 points left, so by induction the statement
holds.

So suppose there isn't such *a*_{i}. There are 3 possibilities:

a_{n}<b_{1}a_{n}=b_{1}a_{n}=b_{j}>b_{1}

We will deal with them in reverse order.

*a*_{n} = *b*_{j} > *b*_{1}

Now *a*_{n} = *b*_{j} is in *M*, so we proceed from *a*_{n − 1},
*a*_{n − 2}, ... to *a*_{1}. We stop when we see an *a*_{i} that's
not in *M*. Let's say we stop at *a*_{n − k} with *k* > 0. Note
we will stop at some point because in *A* there can be at most
|*M*| = *n* − 1 numbers in *M*.

a_{n − k}>b_{1}. We're done because of the lemma.a_{n − k}<b_{1}. So |A∩M| =k> 0, i.e.A∩M= {a_{n},a_{n − 1}, ...,a_{n − k + 1}}. This is the most interesting case to me.

How many points in *M* are larger than *a*_{n}? At most
*n* − 1 − *k* because *k* of them are in the intersection of *M*
and *A*. How many *a*_{i} in *A* are less than *b*_{1}?
*n* − *k*. Therefore, there is at least an *a*_{i} < *b*_{1} such that
*a*_{i} + *a*_{n} is not in *M*. If we put *a*_{i} at [0, *a*_{i}]
and *a*_{n} at [*a*_{i}, *a*_{i} + *a*_{n}], we're sure these two segments have
no end points in *M* because *a*_{i} < *b*_{1} and *a*_{i} + *a*_{n} is
not in *M*, yet they cover at least 2 points in *M*, i.e.
*b*_{1} and *a*_{n} = *b*_{j}. By induction, the remaining
*n* − 2 ≥ 1 segments can be arranged such that no end points fall into
*M*.

*a*_{n} = *b*_{1}

Place *a*_{n} at [0, *a*_{n}]. Let *A*’ = *A* − {*a*_{n}} and
*M*’ = *M* − {*b*_{1}}. By induction we can arrange *A*’ in such a way
that no points in *M*’ coincide with an end point in *A*’. Now only
*b*_{1} touches end points of *a*_{n} and *a*_{j}. Since
*a*_{j} < *a*_{n}, swapping *a*_{j} and *a*_{n} resolves it.

*a*_{n} < *b*_{1}

This is similar. Let's put *a*_{n} at the [0, *a*_{n}]. There are
*n* − 1 segments but *n* − 1 points left, so let's pretend
*b*_{1} doesn't exist. That is, consider *M*’ = *M* − {*b*_{1}}. Now by
induction we can arrange the remaining *n* − 1 segments such that no point
in *M*’ is touched by any end point. Only *b*_{1} might coincide with
an end point of *A* − {*a*_{n}}. Let's assume the current arrangement is

*a*_{n}, *a*_{s1}, *a*_{s2}, ...*a*_{sn − 1}

where *s*_{1}, ..., *s*_{n − 1} is a permutation of {1, ..., *n* − 1}.
Suppose the end points of *a*_{sj}, *a*_{sj + 1} is *b*_{1}. Then we
could rearrange it as

*a*_{s1}, *a*_{s2}, ..., *a*_{sj + 1}, *a*_{n}, *a*_{sj + 2}, *a*_{sj + 3}...

Because *a*_{n} > *a*_{sj + 1}, *b*_{1} is no longer touched by any end
point so we're done.

Q.E.D.

post by Shen-Fu Tsai