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.

Without loss of generality, we assume a[n] > a[n-1] > ... > a[1] >= 1, and denote {a[1], ..., a[n]} by A.

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) a[n] < b[1] (b) a[n] = b[1] (c) a[n] = b[j] > b[1]. We will deal with them in reverse order.

(c)
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.

(i) a[n - k] > b[1]. We're done because of the lemma.
(ii) a[n - k] < b[1]. So |A intersect M| = k > 0, i.e.  A intersect 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.

(b) 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) 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[s[1]], a[s[2]], ... a[s[n - 1]]

where s[1], ... , s[n - 1] is a permutation of {1, ... , n - 1}. Suppose the end points of a[s[j]], a[s[j + 1]] is b[1]. Then we could rearrange it as

a[s[1]], a[s[2]], ... , a[s[j + 1]], a[n], a[s[j + 2]], a[s[j + 3]] ...

Because a[n] > a[s[j + 1]], b[1] is no longer touched by any end point so we're done.

Q.E.D.